暴力思路是从匹配位置 0 开始匹配， 在 wordDict 中一个个找，如果其能和 s 匹配上就尝试进行匹配，并更新匹配位置。
比如 s = "leetcode", wordDict = ["leet", "code"]。
那么：
先试试 leet 可以匹配么？可以的，匹配后 s 剩下 code，继续在 wordDict 中找。
leet 可以匹配么？不能！code 能够匹配么？可以！返回 true 结束
如果 wordDict 遍历一次没有任何进展，那么直接返回 false。
注意到如果匹配成功一次后，本质是把问题规模缩小了，问题性质不变，因此可以使用动态规划来解决。
@cache
def dp(pos):
if pos == len(s): return True
for word in wordDict:
if s[pos:pos+len(word)] == word and dp(pos + len(word)): return True
return False
return dp(0)
class Solution:
def wordBreak(self, s: str, wordDict: List[str]) -> bool:
wordDict = set(wordDict)
@cache
def dp(pos):
if pos == len(s): return True
cur = ''
for nxt in range(pos, len(s)):
cur += s[nxt]
if cur in wordDict and dp(nxt + 1): return True
return False
return dp(0)
JS Code:
/**
* @param {string} s
* @param {string[]} wordDict
* @return {boolean}
*/
var wordBreak = function (s, wordDict) {
const dp = Array(s.length + 1);
dp[0] = true;
for (let i = 0; i < s.length + 1; i++) {
for (let word of wordDict) {
if (word.length <= i && dp[i - word.length]) {
if (s.substring(i - word.length, i) === word) {
dp[i] = true;
}
}
}
}
return dp[s.length] || false;
};
CPP Code:
class Solution {
public:
bool wordBreak(string s, vector<string>& dict) {
unordered_set<string> st(begin(dict), end(dict));
int N = s.size();
vector<bool> dp(N + 1);
dp[0] = true;
for (int i = 1; i <= N; ++i) {
for (int j = 0; j < i && !dp[i]; ++j) {
dp[i] = dp[j] && st.count(s.substr(j, i - j));
}
}
return dp[N];
}
};
