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;
};