140. Word Break II

DFS

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
class Solution {
    public List<String> wordBreak(String s, List<String> wordDict) {
        Set<String> wordSet = new HashSet<>(wordDict);
        List<String> sentenceList = new ArrayList<>();
        List<String> wordList = new ArrayList<>();
        backtrack(sentenceList, wordList, s, wordSet, 0);
        return sentenceList;
    }

    private void backtrack(List<String> sentenceList, List<String> wordList, String s, Set<String> wordSet, int startIndex) {
        if (startIndex == s.length()) {
            sentenceList.add(String.join(" ", wordList));
            return;
        }

        for (int endIndex = startIndex; endIndex < s.length(); endIndex++) {
            // word: s[startIndex, endIndex]
            String word = s.substring(startIndex, endIndex + 1);
            if (wordSet.contains(word)) {
                wordList.add(word);
                backtrack(sentenceList, wordList, s, wordSet, endIndex + 1);
                wordList.remove(wordList.size() - 1);
            }
        }
    }
}

Backtracking + 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
31
32
33
34
35
class Solution {
    public List<String> wordBreak(String s, List<String> wordDict) {
        Set<String> wordSet = new HashSet<>(wordDict);
        Set<Integer> cannotBreakStartIndexCache = new HashSet<>();
        List<String> sentenceList = new ArrayList<>();
        List<String> wordList = new ArrayList<>();
        backtrack(sentenceList, wordList, s, wordSet, 0, cannotBreakStartIndexCache);
        return sentenceList;
    }

    private void backtrack(List<String> sentenceList, List<String> wordList, String s, Set<String> wordSet, int startIndex, Set<Integer> cannotBreakStartIndexCache) {
        if (cannotBreakStartIndexCache.contains(startIndex)) {
            return;
        }
        if (startIndex == s.length()) {
            sentenceList.add(String.join(" ", wordList));
            return;
        }

        int sentenceListSize = sentenceList.size();
        for (int endIndex = startIndex; endIndex < s.length(); endIndex++) {
            // word: s[startIndex, endIndex]
            String word = s.substring(startIndex, endIndex + 1);
            if (wordSet.contains(word)) {
                wordList.add(word);
                backtrack(sentenceList, wordList, s, wordSet, endIndex + 1, cannotBreakStartIndexCache);
                wordList.remove(wordList.size() - 1);
            }
        }

        if (sentenceListSize == sentenceList.size()) {
            cannotBreakStartIndexCache.add(startIndex);
        }
    }
}

References

140. Word Break II