文章目录

• problem
• wrong solution 1 `Brute force recursive`
• solution 2 `dp`
• solution 3 `DFS + prune`

problem

139. Word Break
Given a string s and a dictionary of strings wordDict, return true if s can be segmented into a space-separated sequence of one or more dictionary words.

Note that the same word in the dictionary may be reused multiple times in the segmentation.

Example 1:

Input: s = "leetcode", wordDict = ["leet","code"]
Output: true
Explanation: Return true because "leetcode" can be segmented as "leet code".

Example 2:

Input: s = "applepenapple", wordDict = ["apple","pen"]
Output: true
Explanation: Return true because "applepenapple" can be segmented as "apple pen apple".
Note that you are allowed to reuse a dictionary word.

Example 3:

Input: s = "catsandog", wordDict = ["cats","dog","sand","and","cat"]
Output: false

wrong solution 1 Brute force recursive

class Solution {
public:
    bool recur(int start, string s, unordered_set<string>& word){
        if(start==s.size())return true;
        string sub;
        for(int i=start; i<s.size(); i++)
            if(word.count(sub+=s[i]) && recur(i+1, s, word)) 
                return true;
        return false;
    }
    
    bool wordBreak(string s, vector<string>& wordDict) {
        unordered_set<string> word(wordDict.begin(), wordDict.end());
        return recur(0, s, word);
    }
};

TLE

solution 2 dp

class Solution {
public:
    bool wordBreak(string s, vector<string>& wordDict) {
        int n = s.size();
        vector<bool> dp(n+1, false); 
        unordered_set<string> word(wordDict.begin(), wordDict.end());
    
        dp[n]=true;
        for(int i=n-1; i>=0; i--){
            string sub;
            for(int j=i; j<n; j++){
                if(dp[i]=word.count(sub+=s[j]) && dp[j+1])
                    break;
            }
        }
        return dp[0];
    }
};

solution 3 DFS + prune

class Solution {
public:
    bool recur(int start, string s, unordered_set<string>& word, vector<char>& mem){
        int n = s.size();
        if(start==n)return true;
        if(mem[start] != -1)return mem[start];
        string sub;
        for(int i=start; i<n; i++)
            if(word.count(sub+=s[i]) && recur(i+1, s, word, mem)) 
                return mem[start]=1;
        return mem[start]=0;
    }
    
    bool wordBreak(string s, vector<string>& wordDict) {
        vector<char> mem(s.size(), -1);
        unordered_set<string> word(wordDict.begin(), wordDict.end());
        return recur(0, s, word, mem);
    }
};