Given a non-empty string s and a dictionary wordDict containing a list of non-empty words, determine if s can be segmented into a space-separated sequence of one or more dictionary words.
BackTracking
Brute Force: 2^n => see
TC: (length of s) * (size of wordDict)
SC: n, depth of str
def wordBreak(self, s: str, wordDict: List[str]) -> bool:
visit = [-1] * len(s)
dic = set(wordDict)
return self.backtracking(s, dic, 0, visit)
def backtracking(self, s, dic, start, visit):
if start == len(s): return True
if visit[start] != -1: return visit[start]
for end in range(start+1, len(s)+1):
if s[start:end] in dic and self.backtracking(s, dic, end, visit):
visit[start] = 1
return visit[start]
visit[start] = 0
return visit[start]
DP
State: f[i] 表示前i個字被完美切分
function: f[i] = OR{f[j]}, j<i && j+1 to i is a word
Init: f[0] = true
Ans: f[n]
public boolean wordBreak(String s, List<String> wordDict) {
boolean[] f = new boolean[s.length()+1];
f[0] = true;
for(int i=1; i<=s.length(); i++){ // f length = n+1
for(int j=0; j<i; j++){
if(f[j]){
String sub = s.substring(j, i);
if (wordDict.contains(sub)){
f[i] = true;
break;
}
}
}
}
return f[s.length()];
}
140 Word Break II
Given a non-empty string s and a dictionary wordDict containing a list of non-empty words, add spaces in s to construct a sentence where each word is a valid dictionary word. Return all such possible sentences.
Backtracking
O: (length of s) * (size of wordDict) * (number of answer)
def wordBreak(self, s: str, wordDict: List[str]) -> List[str]:
map = {}
map[len(s)] = ''
dic = set(wordDict)
return self.backtracking(s, 0, map, dic)
def backtracking(self, s, start, map, dic):
if start in map:
return map[start]
res = []
for end in range(start+1, len(s)+1):
if s[start:end] in dic:
for l in self.backtracking(s, end, map, dic):
sen = s[start:end] + (' ' if l != '' else '') + l
res.append(sen)
map[start] = res
return map[start]