Powered By GitBook
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
};
Copied!
Last modified 2yr ago
Copy link