Word Break

Description

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.

Code

Trie

要特別注意

if(cur->isEndofWord && canBreak(root, s, i + 1, memo)){
	memo[start] = 1;
	return true;
}

不能寫成

if(cur->isEndofWord){
	return memo[start] = canBreak(root, s, i + 1, memo);
}

考慮例子：s = “aaaaaaa”, wordDict = [“aaaa”, “aaa”] 就知道了。

class TrieNode {
public:
    char character;
    bool isEndofWord;
    TrieNode* children[26];
    TrieNode(char c): character(c), isEndofWord(false) {
        for(int i = 0; i < 26; i++) {
            children[i] = nullptr;
        }
    }
};
 
class Solution {
public:
 
    void insertWord(TrieNode* node, string& s) {
        TrieNode* cur = node;
        for(auto c: s) {
            int i = c - 'a';
            if(cur->children[i] == nullptr) {
                cur->children[i] = new TrieNode(c);
            }
            cur = cur->children[i];
        }
        cur->isEndofWord = true;
    }
 
    bool canBreak(TrieNode* root, string& s, int start, vector<int>& memo) {
        
        if(start == s.size()) {
            return true;
        }
 
        if(memo[start] != -1)
            return memo[start];
 
        TrieNode* cur = root;
        for(int i = start; i < s.size(); i++) {
            int index = s[i] - 'a';
            if(cur->children[index] == nullptr) {
                memo[start] = 0;
                return false;
            }
            cur = cur->children[index];
            if(cur->isEndofWord && canBreak(root, s, i + 1, memo)){
                memo[start] = 1;
                return true;
            }
        }
 
        memo[start] = 0;
        return false;
    }
 
    bool wordBreak(string s, vector<string>& wordDict) {
        TrieNode* root = new TrieNode('a');
 
        for(auto& word: wordDict) {
            insertWord(root, word);
        }
        int n = s.size();
        vector<int> memo(n, -1);
 
        return canBreak(root, s, 0, memo);
    }
};

Brute Force

$O (2^{n})$ , TLE

$T (n) = T (n - 1) + T (n - 2) + \dots$ $T (n - 1) = T (n - 2) + T (n - 3) + \dots$ $T (n) - T (n - 1) = T (n - 1) \Rightarrow T (n) = 2 T (n - 1) \Rightarrow T (n) = O (2^{n})$

最簡單的分析是：每個 index 都可以被當作斷點，可斷可不斷，總共兩種選擇，所以 $2^{n}$

class Solution {
public:
    bool wordBreak(string s, vector<string>& wordDict) {
        unordered_set<string> st(wordDict.begin(), wordDict.end());
        return wb(s, st);
    }
 
    bool wb(string s, unordered_set<string>& st) {
        if(s.length() == 0) return true;
        for(int i = 1; i <= s.length(); i++) {            
            if(st.count(s.substr(0, i)) > 0 && wb(s.substr(i), st)) {
                return true;
            }
        }
 
        return false;
    }
};

With Memo

class Solution {
public:
    bool wordBreak(string s, vector<string>& wordDict) {
        unordered_set<string> st(wordDict.begin(), wordDict.end());
        vector<int> mem(s.length(), -1);
        return wb(s, 0, st, mem);
    }
 
    bool wb(string& s, int start, unordered_set<string>& st, vector<int>& mem) {
        if(start == s.length()) return 1;
        if(mem[start] != -1) return mem[start];
        string temp = "";
        for(int i = start; i < s.length(); i++) {     
            temp += s[i];       
            if(st.count(temp) > 0 && wb(s, i + 1, st, mem)) {
                return mem[start] = 1;
            }
        }
 
        return mem[start] = 0;
    }
};

DP

注意 for loop 的 index， dp[0] = true;（例如 leetcode 的 leet 要是 true，代表去掉 leet 後的空字串要是 true），且 i - j 剛好就是 substring 的長度。

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

Source

Word Break - LeetCode

Jimmy Lin's Blog

Explorer