题目描述

给定一个非空字符串ss和一个非空词典wordDictwordDict,判断ss是否能被分割成一个或多个单词分隔的序列。

注意，词典中的词可以用多次，词典中没有重复的单词。

样例

Example 1:

输入: s = "leetcode", wordDict = ["leet", "code"]
输出: true
解释:  "leetcode" 可以被切割成 "leet code"

Example 2:

输入: s = "applepenapple", wordDict = ["apple", "pen"]
输出: true
解释: "applepenapple" 可以被切割成 "apple pen apple"

Example 3:

输入: s = "catsandog", wordDict = ["cats", "dog", "sand", "and", "cat"]
输出: false

算法1

(brute force with recursion) $O(n^n)$

check every possible prefix of that string in the dictionary of words, if it is found in the dictionary, then the recursive function is called for the remaining portion of that string.

base case: if in some function call it is found that the complete string is in dictionary, then it will return true.

时间复杂度分析：worst case sssssss, every prefix is present in the dictionary of words, then the recursion tree can grow upto $O(n^n)$

C++ 代码

class Solution {
public:
    bool wordBreak(string s, vector<string>& wordDict) {
        if(wordDict.size()==0) return false;
        set<string> _wordDict;
        for(auto &x: wordDict){
            _wordDict.insert(x);
        }
        return _wordBreak(s, _wordDict, 0);
    }
    bool _wordBreak(string s, set<string> _wordDict, int start){
        if(start == s.length())
            return true;
        for(int j = 0; start + j <= s.length(); j++){
            if(_wordDict.count(s.substr(start, j)) && _wordBreak(s, _wordDict, start + j)){
                return true;
            }
        }
        return false;
    }
};
class Solution {
public:
    bool wordBreak(string s, vector<string>& wordDict) {
        return _wordBreak(s, wordDict, 0);
    }
    bool _wordBreak(string s, vector<string> wordDict, int start){
        if(start == s.length())
            return true;
        for(auto w: wordDict){
            int end = start + w.size()-1;
            if(end < s.length() && s.substr(start, w.size()) == w){
                if(start + w.size() == s.length())
                    return true;
                else if(_wordBreak(s, wordDict, end+1))
                    return true;
            }
        }       
        return false;
    }
};

算法2

(Recursion with memoization) $O(n^2)$

use a set memo to store the false subproblems so that when the recursive function is called with a case we have eevaluated before, we can directly return false without redundant calculation.

the prefix must be true then the recursive function is called. there is no need to store the end index returning true.

时间复杂度分析：$O(n^2)$

C++ 代码

class Solution {
public:
    vector<string> _wordDict;
    set<int> vis;
    bool wordBreak(string s, vector<string>& wordDict) {
        _wordDict = wordDict;
        return _wordBreak(s, 0);
    }
    bool _wordBreak(string s, int start){
        for(auto &w: _wordDict){
            int end = start + w.length()-1;
            if(end < s.length() && s.substr(start, w.size()) == w){
                if(start + w.size() == s.size())
                    return true;
                else if(vis.find(end) != vis.end())
                    return false;
                else if(_wordBreak(s, end+1))
                    return true;
                else vis.insert(end);
            }
        }
        return false;
    }
};

算法3

(bfs) $O(n^2)$

Think the string as a tree, where each node is a prefix/word. Two nodes are connected only if the two words are included in the dict.

The traverse start from the first character of the string and find every possible substring starting with that character. The end index of each word would be pushed in the queue.

If we are able to obtain the last element of the given string as a node (leaf) of the tree, this implies that the given string can be partitioned into substrings which are all a part of the given dictionary.

Use a memo to store some results otherwise would TLE.

时间复杂度分析：$O(n^2)$

C++ 代码

// bfs
class Solution {
public:
    bool wordBreak(string s, vector<string>& wordDict) {
        queue<int> prefixQ;
        set<int> vis; //memo
        prefixQ.push(0);
        while(!prefixQ.empty()){
            int start = prefixQ.front();
            prefixQ.pop();
            if(vis.find(start) == vis.end()){
                for(auto w: wordDict){
                        int end = start + w.size()-1;
                        if(end < s.length() && s.substr(start, w.size()) == w){
                            if(start + w.size() == s.size())
                                return true;
                            else {
                                prefixQ.push(end+1);
                            }                        
                        }   
                }
                vis.insert(start);
            }
        }
        return false;
    }   
};

算法4

(dp) $O(n^2)$

dp 隔板
注意substr(j, i-j)

时间复杂度分析：$O(n^2)$

C++ 代码

// dp
class Solution {
public:
    bool wordBreak(string s, vector<string>& wordDict) {
        set<string> _wordDict(wordDict.begin(), wordDict.end());
        vector<bool> dp(s.size()+1, false);
        dp[0] = true;
        for(int i = 0; i <= s.size(); i++){
            for(int j = i; j >= 0; j--){
                if(dp[j]){
                    string word = s.substr(j,i-j);
                    if(_wordDict.find(word)!= _wordDict.end()){
                        dp[i]=true;
                        break; 
                    }
                }

            }
        }
        return dp[s.size()];
    }
};