139.Word Break

139.Word Break

给定一个非空字符串 s 和一个包含非空单词列表的字典 wordDict，判定 s 是否可以被空格拆分为一个或多个在字典中出现的单词。

说明： 拆分时可以重复使用字典中的单词。 你可以假设字典中没有重复的单词。

示例 1：
输入: s = "leetcode", wordDict = ["leet", "code"]
输出: true
解释: 返回 true 因为 "leetcode" 可以被拆分成 "leet code"。
示例 2：

输入: s = "applepenapple", wordDict = ["apple", "pen"]
输出: true
解释: 返回 true 因为 "applepenapple" 可以被拆分成 "apple pen apple"。
     注意你可以重复使用字典中的单词。
示例 3：

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

方法：

1. 最直观的想法是暴力判断，从第一个字符开始，找到剩下的所有字符在字典中的情况。如果没找到，则返回false。代码如下：

class Solution {
private:
    unordered_map<string,int> dict;
    bool dictbreak(string s)
    {
        if(dict[s]) return true;
        for(int i=1;i<s.length();i++)
        {
            string tmp=s.substr(0,i);
            if(dict[tmp] && dictbreak(s.substr(i,s.length()-i)))
                return true;
        }
        return false;
    }
public:
    bool wordBreak(string s, vector<string>& wordDict) {
        for(int i=0;i<wordDict.size();i++)
            dict[wordDict[i]]++;
    
        return dictbreak(s);
    }
    
};

结果超时啦～算算时间复杂度吧，主要影响时间的是dictbreak函数中的循环里的递归调用，设字符串长度为n，计算次数（只考虑循环）为T(n),则T(n)=1+T(n-1)+1+T(n-2)+...+1+T(1)+1+T(0); 其中，T(0)=0,T(1)=1， 则T(n)=sigma(T(n-1))+n; 所以，sigma(T(n)) = sigma(T(n-1))+T(n)=n+2sigma(T(n-1)); 因此有，sigma(T(n)) +n =2sigma(T(n-1))+2(n-1)+2; 递归一下，有sigma(T(n))+n = 2^(n-1) x sigma(T(1)+1)+sigma(2^(n-1)=O(2^n); 由于T(n)和sigma(T(n-1))+n复杂度相同，所以时间复杂度为指数级别。。。 当然不会通过。

1. 从右侧开始判断，将左侧判断过的放入内存中，之后不必再次判断。一样采用递归的方法。 代码如下：

class Solution {
public:
    bool wordBreak(string s, vector<string>& wordDict) {
        unordered_set<string> dict(wordDict.cbegin(),wordDict.cend());
        
        return wordBreak(s,dict);
    }
    bool wordBreak(string s, const unordered_set<string>& wordDict) {
        if(mem.count(s)) return mem[s];
        if(wordDict.count(s)) return mem[s]=true;
        for(int i=0;i<s.length();i++)
        {
            const string left=s.substr(0,i);
            const string right=s.substr(i);
            if(wordDict.count(right) && wordBreak(left,wordDict))
                return mem[s]=true;
        }
        return mem[s]=false;
    }
private:
    unordered_map<string,bool> mem;
};

此时时间复杂度为O(n^2) 最后给出leetcode排名比较靠前的一种解法:

class Solution {
public:
    bool wordBreak(string s, vector<string>& wordDict) {
        if(s.empty()){
            return true;
        }
        for(auto s:wordDict){
            wordset.insert(s);
            if(s.size()>maxl){
                maxl=s.size();
            }
        }
        vector<bool>flag(s.size()+1,false);
        flag[0]=true;
        for(int i=0;i<s.size();i++){
          for(int j=0;j<min(maxl,i+1);j++){
                if(flag[i-j]&&(wordset.find(s.substr(i-j,j+1))!=wordset.end())){
                    flag[i+1]=true;
                    break;
                }
        }
        }
        return flag[s.size()];
    }
private:
    unordered_set<string> wordset;
    int maxl=0;
};