单词拆分

2025/10/16

思路：先观察字典里的词有没有包含关系，如果有，则先考虑最小子词。 如果是都互不包含，则按照KMP算法，并行地匹配字典中的所有能匹配的词。如果不能匹配断掉了，则false，如果能撑到最后，则true。

评价：搞麻烦了。

推荐答案：动态规划，dp[i]表示s的前i个字符能否拆分成字典中的词。转移方程：dp[i] = dp[j] and (s[j:i] in wordDict) for j in [0, i)。这个转移方程很有意思，它是之前所有的dp值的函数，所以这样的动态规划是存在可行的。不要一看很麻烦就觉得不是动态规划，仔细想想。