Notebook online

单词拆分

 算法

今天继续手撕算法，这两天新做的，也属于是面试高频题了，特别是单词拆分II，周赛的味儿太重了，动不动就超时

单词拆分I

题目链接

wordbreak1.png

看到这题自然而然想到遍历，先用常规的暴力解法DFS和BFS来试一试，不出意外结果超时了emm

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22

//BFS
class Solution {
    public boolean wordBreak(String s, List<String> wordDict) {
        Set<String> setDict = new HashSet<>(wordDict);
        //记录当前层开始遍历字符串s的位置
        Queue<Integer> queue = new LinkedList<>();
        queue.add(0);   
        int length = s.length();
        while (!queue.isEmpty()) {
            int index = queue.poll();
            //如果字符串到遍历完了，自己返回true
            if (index == length)
            return true;
        for (int i = index + 1; i <= length; i++) {
            if (setDict.contains(s.substring(index, i))) {
                queue.add(i);
            }
        }
    }
        return false;
    }
}

超时◎ timeout QAQ

动态规划

我们又想到了动态规划，首先我们来看看dp的思考过程：

  1. 确定问题的子结构

检查字符串的前缀是否可以由字典中的单词组成

  1. 确定状态

定义状态dp[i]来表示字符串s的前i个字符是否可以被字典中的单词组成

  1. 确定状态转移方程
dp[i] = true，如果存在一个j（0 <= j < i），使得dp[j]是true，并且s的子串s[j:i]在字典中
  1. 确定初始状态和边界情况 初始状态定义为dp[0] = true，意味着存在没有使用任何单词的情况
优化
  • 迭代过程中，如果发现dp[i] == true ，直接break，其中在时间上通过限制内层循环的长度和提前退出循环增加了一些效率
代码
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22

class Solution {
    public boolean wordBreak(String s, List<String> wordDict) {
        int len = s.length(), maxw = 0;
        boolean[] dp = new boolean[len + 1]; 
        dp[0] = true;
        Set<String> set = new HashSet();
        for(String str : wordDict){
            set.add(str);
            maxw = Math.max(maxw, str.length());
        }
        for(int i = 1; i < len + 1; i++){
            for(int j = i; j >= 0 && j >= i - maxw; j--){
                if(dp[j] && set.contains(s.substring(j, i))){
                    dp[i] = true;
                    break;
                }
            }
        }
        return dp[len];

    }
}

时间复杂度O(n)

空间复杂度O(n)

DFS+记忆化

通过上面timeout的示例，我们可以看到做了大量重复计算

优化

创建一个HashMap 'memo' 用来存储已经解决的子问题结果，用start作为指针代表当前节点的状态，从start位置开始，尝试每一个i，如果字串s(start,i)在字典中，并且剩余的字符串可以成功分割则返回true，如果start的结果已经在memo中，直接返回结果即可，当start等于字符串长度，表示成功到达字符串末尾

代码
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27

class Solution {
    public boolean canBreak(int start, String s, Set<String> wordSet, HashMap<Integer, Boolean> memo) {
        if (start == s.length()) {
            return true;
        }
        if (memo.containsKey(start)) {
            return memo.get(start);
        }

        for (int i = start + 1; i <= s.length(); i++) {
            String prefix = s.substring(start, i);
            if (wordSet.contains(prefix) && canBreak(i, s, wordSet, memo)) {
                memo.put(start, true);
                return true;
            }
        }

        memo.put(start, false);
        return false;
    }

    public boolean wordBreak(String s, List<String> wordDict) {
        Set<String> wordSet = new HashSet<>(wordDict);
        HashMap<Integer, Boolean> memo = new HashMap<>();
        return canBreak(0, s, wordSet, memo);
    }
}

时间复杂度：O(n^2*m) 其中n是字符串s的长度，m是字典中最长单词的长度

空间复杂度：O(n)

单词拆分II

题目链接

wordbreak1.png

DFS+回溯

II相比于I，不仅要判断解是否存在，还要列出所有可能的解

分析

递归的基条件是检查起始位置start是否已经到达字符串s的末尾。如果是，就将当前路径添加到结果列表中。在每次递归中，遍历单词字典，尝试将每个单词作为当前位置的前缀。如果成功，将该单词添加到当前路径中，并递归地调用dfs处理剩下的字符串。在每次递归调用dfs后，需要从当前路径中移除最后添加的单词，这确保了当前路径始终反映了到当前递归深度为止的所有有效选择，每当找到一个有效的单词组合时，就将其以字符串形式添加到结果列表中。

代码
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22

class Solution {
    public List<String> wordBreak(String s, List<String> wordDict) {
        List<String> results = new ArrayList<>();
        dfs(s, wordDict, 0, new ArrayList<>(), results);
        return results;
    }

    private void dfs(String s, List<String> wordDict, int start, List<String> current, List<String> results) {
        if (start == s.length()) {
            results.add(String.join(" ", current));
            return;
        }

        for (String word : wordDict) {
            if (start + word.length() <= s.length() && s.substring(start, start + word.length()).equals(word)) {
                current.add(word);
                dfs(s, wordDict, start + word.length(), current, results);
                current.remove(current.size() - 1);  // 回溯
            }
        }
    }
}

相关文章：