139. 单词拆分

dp[i] = s[0..i) 可被拆分。

难度：中等。题型：DP。

标签：字符串、动态规划、哈希表、高频面试

一维 DP：dp[i]=any(dp[i-len(w)]&&substring matches w)。 时间复杂度 O(n^2)，空间复杂度 O(n)。