/ Data Structure and Algorithms  

Leetcode 139. Word Break

Question



Give a string, and some words, and determine if the string can be composed of these words. Each word can be used multiple times or not.

Similar Questions

Solution

Divide and conquer, big problems are converted into small problems and solved by small problems.

We now need to determine whether the target string s can be composed of wordDict.

Use canBreak[i] to indicate whether the substring s[0, i) can be composed of wordDict.

Suppose we know canBreak[1], canBreak[2], canBreak[2], … canBreak[len - 1], that is, whether all substrings except s can be composed of wordDict.

Then we can know

1
2
3
4
5
canBreak[len] =  canBreak[1] && wordDict.contains(s[1,len))
            || canBreak[2] && wordDict.contains(s[2,len))
            || canBreak[3] && wordDict.contains(s[3,len))   
            ...
            || canBreak[len - 1] && wordDict.contains(s[len - 1,len))

canBreak[len] represents whether s can be composed of wordDict.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
public boolean wordBreak(String s, List<String> wordDict) {
    // want to know if canBreak[s.length] is true
    boolean[] canBreak = new boolean[s.length() + 1];

    canBreak[0] = true;

    for (int i = 1; i <= s.length(); i++) {
        // if canBreak[i] is true, then must canBreak[j] and substring(j, i) in wordDict
        for (int j = 0; j < i; j++) {
            canBreak[i] = canBreak[j] && wordDict.contains(s.substring(j, i));

            if (canBreak[i]) {
                break;
            }
        }
    }

    return canBreak[s.length()];
}