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;
};
Last modified 1yr ago