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值的函数,所以这样的动态规划是存在可行的。不要一看很麻烦就觉得不是动态规划,仔细想想。