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
19
20
21
class Solution {
    public boolean wordBreak(String s, List<String> wordDict) {
        int n = s.length();

        Set<String> wordSet = new HashSet<>(wordDict);

        // 定义 dp[i] 为子字符串 s[0, i - 1] 是否能由 wordDict 组成
        boolean[] dp = new boolean[n + 1];
        dp[0] = true;

        for (int i = 1; i <= n; i++) {
            // split to: [0, j] / [j + 1, i]
            // 从前 j 个字符处分割
            for (int j = 0; j < i && !dp[i]; j++) {
                dp[i] |= dp[j] && wordSet.contains(s.substring(j, i));
            }
        }

        return dp[n];
    }
}

References

139. Word Break