动态规划 回溯 记忆化回溯 139.单词拆分

动态规划题解：

求：dp[s.length]，dp长度是n+1，存放boolean值
1）定义dp数组：dp[i]：长度为 i 的 s[0:i-1] 子串是否能拆分成单词，是一个 Boolean 值。
2）初始化及basecase：初始化 dp[0]=True 空字符可以被表示
3）状态转移：
s[0:i] 子串的 dp[i+1] 是否为真（是否可拆分成单词），取决于两点：
它的前缀子串 s[0:j-1] 的 dp[j] ，是否为真。
剩余子串 s[j:i]，是否是一个独立的单词。

solution：

class Solution {
    public boolean wordBreak(String s, List<String> wordDict) {
        int n=s.length();
        boolean[] dp=new boolean[n+1];
        dp[0]=true;
        for(int i=1;i<=n;i++){
           for(int j=0;j<i;j++){
               if(dp[j]&&wordDict.contains(s.substring(j,i))){
                   dp[i]=true;
                   break;// i长度的子串已经可以break成单词了，不需要j继续划分子串了
               }
           }
        }
       return dp[n];
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16

回溯题解：

将字典加入到set中，逐渐增加字符直到匹配到set中的单词，再递归判断剩下的字符串，无法匹配返回false，最后剩下空则说明全部匹配。subString生成了新的字符串对象，因此不会对原来的字符串产生影响

substring(i)返回值是 str的索引位置i，到最大索引（两个索引都包括）

超时

class Solution {
    public boolean backtrack(String s, Set<String> set) {
        if (s.length() == 0) return true;
        for (int i = 0; i < s.length(); i++) {
            if (set.contains(s.substring(0, i + 1))){
                if (backtrack(s.substring(i + 1), set)) return true;
            }
        }
        return false;
    }
    public boolean wordBreak(String s, List<String> wordDict) {
        Set<String> set = new HashSet<>(wordDict);
        return backtrack(s, set);
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15

记忆化回溯题解：

增加一个boolean数组表示当前位置之后的字符串是否遍历过了
如果遍历过了并且没有提前递归的返回true说明这个位置后面的匹配是不会成功的，因此直接返回false

class Solution {
    boolean[] mem;
    public boolean backtrack(String s, int start, Set<String> set) {
        if (s.length() == 0) return true;
        if (mem[start]) return false;
        for (int i = 0; i < s.length(); i++) {
            if (set.contains(s.substring(0, i + 1))){
                if (backtrack(s.substring(i + 1), start + i + 1, set)) return true;
            }
        }
        mem[start] = true;
        return false;
    }
    public boolean wordBreak(String s, List<String> wordDict) {
        this.mem = new boolean[s.length()];
        Set<String> set = new HashSet<>(wordDict);
        return backtrack(s, 0, set);
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19