0139. 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

Constraints:

• 1 <= s.length <= 300
• 1 <= wordDict.length <= 1000
• 1 <= wordDict[i].length <= 20
• s and wordDict[i] consist of only lowercase English letters.
• All the strings of wordDict are unique.

cpp: dfs with memo

class Solution {
public:
    unordered_map<string, bool> memo;

    bool wordBreak(string s, vector<string>& wordDict) {
        unordered_set<string> dict(wordDict.begin(), wordDict.end());
        return dfs(s, dict);
    }

    bool dfs(string s, unordered_set<string>& dict) {
        if (memo.count(s))
            return memo[s];
        if (dict.count(s))
            return memo[s] = true;
        for (int i = 1; i < s.size(); ++i) {
            if (dict.count(s.substr(0, i)) == 0) // cannot split from here
                continue;
            if (dfs(s.substr(i), dict)) // 0-i do exist, now check the rest
                return memo[s] = true;
        }
        return memo[s] = false; // has tried all options
    }
};

java: dp

public class Solution {
    public boolean wordBreak(String s, Set<String> dict) {

        boolean[] f = new boolean[s.length() + 1];

        f[0] = true;


        /* First DP
        for(int i = 1; i <= s.length(); i++){
            for(String str: dict){ // check each element in dp
                if(str.length() <= i){
                    if(f[i - str.length()]){ // complement exist
                        if(s.substring(i-str.length(), i).equals(str)){
                            f[i] = true;
                            break;
                        }
                    }
                }
            }
        }*/

        //Second DP
        for(int i=1; i <= s.length(); i++){
            for(int j=0; j < i; j++){ // split current s into s[0:j] and s[j:i]
                if(f[j] && dict.contains(s.substring(j, i))){
                    f[i] = true;
                    break;
                }
            }
        }

        return f[s.length()];
    }
}

f[i] stands for whether subarray(0, i) can be segmented into words from the dictionary. So f[0] means whether subarray(0, 0) (which is an empty string) can be segmented, and of course the answer is yes.

The default value for boolean array is false. Therefore we need to set f[0] to be true.

cpp with optimization

class Solution {
public:
    bool wordBreak(string s, vector<string>& word) {
        int n = s.size();
        vector<bool> dp(n+1);
        dp[0] = true;
        for(int i=0; i<n; i++) if(dp[i]) { // only consider if s[0:i] already exists
            for(auto &str: word) {
                int l = str.size();
                if(s.substr(i, l) == str) 
                    dp[i+l] = true; // s[0:i] and s[i+str.size()] all valid
            }
        }
        return dp.back();
    }
};

instead of comparing with the rest from s, compare with the word dict.

---

Last update: April 1, 2022