Word Break

• State: f[i]表示前i个位置/数字/字符,第i个...

• 一般answer是f(n)而不是f(n-1)

139. Word Break

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 explain

• 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]