139.Word Break

Posted on | In

Test cases

1
2
3
4
5
6
7
8
9
10
"hello"
[]
"leetcode"
["leet","code"]
"cars"
["car", "ca", "rs"]
"aaaaaaa"
["aaaa", "aaa"]
"y"
["ye"]

Solution 1: accepted 13ms

DP. Still need to look back.
Time: O(n^3), two for loop and s.substring()
Space: O(n) 

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
public boolean wordBreak(String s, List<String> wordDict) {
  int len = s.length();
  boolean[] dp = new boolean[s.length() + 1];
  dp[0] = true;
  for(int i = 1; i <= len; i++) {
    for(int j = 0; j < i; j++) {
      if (dp[j] && wordDict.contains(s.substring(j, i))) {
        dp[i] = true;
        break;
      }
    }
  }
  return dp[len];
}

Solution 2

Based on the list. We could use this one if the list is very long, since solution 1 needs to iterate the entire list all the time.

Time: O(n^2)
Space: O(n)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
public boolean wordBreak(String s, List<String> wordDict) {
    int len = s.length();
    boolean[] dp = new boolean[s.length()+1];
    dp[0] = true;
    for (int i = 1; i <= len; i++){
        for (String str : wordDict){
            if (str.length() <= i){ // so that str could be a possible solution
                if (dp[i - str.length()]){ // the head has to be true
                    if (s.substring(i-str.length(), i).equals(str)){ // verify whether the tail is equal to str
                        dp[i] = true;
                        break;
                    }
                }
            }
        }
    }
    return dp[len];
}