思路:f[i]表示从1-i字符串s是否可以拆分,那么可以得出如果f[i]可以拆分时,我们枚举i+1——n组成的字符串中有没有出现再字典里的如果i+1——j构成的字符串出现过则说明,f[j]可以拆分。我们手写一个字符串hash表,原理是将将字符串变成一个P进制数
代码:
class Solution {
public:
bool wordBreak(string s, vector<string>& wordDict) {
typedef unsigned long long ull;
const int P=131;
unordered_set<int> hash;
for(auto& word:wordDict){
ull h=0;
for(auto c:word) h=h*P+c;
hash.insert(h);
}
int n=s.size();
vector<bool> f(n+1);
s=' '+s;
f[0]=true;
for(int i=0;i<n;i++){
if(f[i]){
ull h=0;
for(int j=i+1;j<=n;j++){
h=h*P+s[j];
if(hash.count(h)) f[j]=true;
}
}
}
return f[n];
}
};