Poison

139. Word Break

发表于
DFS(TLE)
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
class Solution {
    public boolean wordBreak(String s, List<String> wordDict) {
        Set<String> wordSet = new HashSet<>(wordDict);
        return dfs(s, wordSet, 0);
    }

    private boolean dfs(String s, Set<String> wordSet, int startIndex) {
        if (startIndex == s.length()) {
            return true;
        }

        for (int endIndex = startIndex; endIndex < s.length(); endIndex++) {
            // word: s[startIndex, endIndex]
            if (wordSet.contains(s.substring(startIndex, endIndex + 1)) && dfs(s, wordSet, endIndex + 1)) {
                return true;
            }
        }

        return false;
    }
}
DFS + Cache
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
28
29
30
class Solution {
    public boolean wordBreak(String s, List<String> wordDict) {
        Set<String> wordSet = new HashSet<>(wordDict);
        Set<Integer> cannotBreakStartIndexSet = new HashSet<>();
        return dfs(s, 0, wordSet, cannotBreakStartIndexSet);
    }

    private boolean dfs(String s, int startIndex, Set<String> wordSet, Set<Integer> cannotBreakStartIndexSet) {
        if (cannotBreakStartIndexSet.contains(startIndex)) {
            return false;
        }

        if (startIndex == s.length()) {
            return true;
        }

        // word: s[startIndex, endIndex]
        for (int endIndex = startIndex; endIndex < s.length(); endIndex++) {
            String word = s.substring(startIndex, endIndex + 1);
            if (wordSet.contains(word)) {
                if (dfs(s, endIndex + 1, wordSet, cannotBreakStartIndexSet)) {
                    return true;
                }
            }
        }

        cannotBreakStartIndexSet.add(startIndex);
        return false;
    }
}
DP
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) {
        // 定义 dp[i][j] 为子串 s[i...j] 是否可由字典中的单词拼接出来
        // 当不拆分时，判断 wordDict 是否包含 s[i...j]
        // 当拆分时，遍历分割点 k, dp[i][j] = dp[i][k] && dp[k + 1][j] 
        boolean[][] dp = new boolean[s.length()][s.length()];

        Set<String> wordSet = new HashSet<>(wordDict);
        for (int i = s.length() - 1; i >= 0; i--) {
            for (int j = i; j < s.length(); j++) {
                if (wordSet.contains(s.substring(i, j + 1))) {
                    dp[i][j] = true;
                }
                for (int k = i; !dp[i][j] && k < j; k++) {
                    dp[i][j] = dp[i][k] && dp[k + 1][j];
                }
            }
        }

        return dp[0][s.length() - 1];
    }
}
DP
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
class Solution {
    public boolean wordBreak(String s, List<String> wordDict) {
        Set<String> wordSet = new HashSet<>(wordDict);

        // 定义 dp[i] 为前 i 个字符组成的子串是否可由字典拼接而成
        boolean[] dp = new boolean[s.length() + 1];
        dp[0] = true;

        for (int i = 1; i <= s.length(); i++) {
            // k 为分割点，表示前 k 个字符
            for (int k = 0; !dp[i] && k < i; k++) {
                dp[i] = dp[k] && wordSet.contains(s.substring(k, i));
            }
        }

        return dp[s.length()];
    }
}
Reference

139. Word Break