幸对清风皓月
苔茵展
云幕高张
这种一看就是dp的题，我都直接先用暴力dfs解一遍，暴力思路：每次匹配遍历wordDict中所有的单词，然后取到合适的单词（能够匹配上字符串的开头），就将字符串的开头去掉，然后进入下一层函数。。。最后字符串为空，就返回true，如果遍历wordDict中所有的单词，没有能够匹配字符串开头的，就直接返回false。
代码比较简洁，缺点就是超时：
class Solution {
private:
bool dfs(const char *s, const vector<string> &word_dict) {
if (*s == '\0')
return true;
for (const string &it : word_dict) {
size_t len = it.length();
if (strncmp(s, it.c_str(), len) == 0) {
if (dfs(s + len, word_dict))
return true;
}
}
return false;
}
public:
bool wordBreak(string s, vector<string> &wordDict) {
return dfs(s.c_str(), wordDict);
}
};
然后就是dp的思路。
dp也不难想到，有点像经典题跳楼梯那个。
如果整个字符串s能被wordDict构造，那就相当于存在某个相对s中缺失末尾单词word的字符串ss，同时word是wordDict中的元素。其实就是ss + word == s, word in wordDict。
那如果用dp来解释就是下面的公式，其中dp(x)代表s从开头依次取x字符组成的字符串是否能够被wordDict组合而成，w就是word：
公式描述的可能不太清除，看代码就很明了了。。。
class Solution {
public:
bool wordBreak(string s, vector<string> &wordDict) {
int len = s.length();
vector<bool> dp(len + 1);
dp[0] = true;
for (int i = 1; i <= len; i++) {
for (const string &it : wordDict) {
int wordlen = it.length();
if (i - wordlen >= 0 && dp[i - wordlen] && strncmp(s.c_str() + i - wordlen, it.c_str(), wordlen) == 0) {
dp[i] = true;
break;
}
}
}
return dp.back();
}
};
