139.Word Break

139.Word Break
给定一个非空字符串 s 和一个包含非空单词列表的字典 wordDict，判定 s 是否可以被空格拆分为一个或多个在字典中出现的单词。
说明： 拆分时可以重复使用字典中的单词。 你可以假设字典中没有重复的单词。
1
示例 1：
2
输入: s = "leetcode", wordDict = ["leet", "code"]
3
输出: true
4
解释: 返回 true 因为 "leetcode" 可以被拆分成 "leet code"。
5
示例 2：
6
​
7
输入: s = "applepenapple", wordDict = ["apple", "pen"]
8
输出: true
9
解释: 返回 true 因为 "applepenapple" 可以被拆分成 "apple pen apple"。
10
     注意你可以重复使用字典中的单词。
11
示例 3：
12
​
13
输入: s = "catsandog", wordDict = ["cats", "dog", "sand", "and", "cat"]
14
输出: false
Copied!
方法：
1.最直观的想法是暴力判断，从第一个字符开始，找到剩下的所有字符在字典中的情况。如果没找到，则返回false。代码如下：
1
class Solution {
2
private:
3
    unordered_map<string,int> dict;
4
    bool dictbreak(string s)
5
    {
6
        if(dict[s]) return true;
7
        for(int i=1;i<s.length();i++)
8
        {
9
            string tmp=s.substr(0,i);
10
            if(dict[tmp] && dictbreak(s.substr(i,s.length()-i)))
11
                return true;
12
        }
13
        return false;
14
    }
15
public:
16
    bool wordBreak(string s, vector<string>& wordDict) {
17
        for(int i=0;i<wordDict.size();i++)
18
            dict[wordDict[i]]++;
19
    
20
        return dictbreak(s);
21
    }
22
    
23
};
Copied!
结果超时啦～算算时间复杂度吧，主要影响时间的是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.从右侧开始判断，将左侧判断过的放入内存中，之后不必再次判断。一样采用递归的方法。 代码如下：
1
class Solution {
2
public:
3
    bool wordBreak(string s, vector<string>& wordDict) {
4
        unordered_set<string> dict(wordDict.cbegin(),wordDict.cend());
5
        
6
        return wordBreak(s,dict);
7
    }
8
    bool wordBreak(string s, const unordered_set<string>& wordDict) {
9
        if(mem.count(s)) return mem[s];
10
        if(wordDict.count(s)) return mem[s]=true;
11
        for(int i=0;i<s.length();i++)
12
        {
13
            const string left=s.substr(0,i);
14
            const string right=s.substr(i);
15
            if(wordDict.count(right) && wordBreak(left,wordDict))
16
                return mem[s]=true;
17
        }
18
        return mem[s]=false;
19
    }
20
private:
21
    unordered_map<string,bool> mem;
22
};
Copied!
此时时间复杂度为O(n^2) 最后给出leetcode排名比较靠前的一种解法:
1
class Solution {
2
public:
3
    bool wordBreak(string s, vector<string>& wordDict) {
4
        if(s.empty()){
5
            return true;
6
        }
7
        for(auto s:wordDict){
8
            wordset.insert(s);
9
            if(s.size()>maxl){
10
                maxl=s.size();
11
            }
12
        }
13
        vector<bool>flag(s.size()+1,false);
14
        flag[0]=true;
15
        for(int i=0;i<s.size();i++){
16
          for(int j=0;j<min(maxl,i+1);j++){
17
                if(flag[i-j]&&(wordset.find(s.substr(i-j,j+1))!=wordset.end())){
18
                    flag[i+1]=true;
19
                    break;
20
                }
21
        }
22
        }
23
        return flag[s.size()];
24
    }
25
private:
26
    unordered_set<string> wordset;
27
    int maxl=0;
28
};
29
    
Copied!

131.Palindrome Partitioning

140.Word Break II

Last modified 5mo ago

Copy link