Description
Given a string s and a dictionary of words dict, determine if s can be break into a space-separated sequence of one or more dictionary words.
Example
Example 1:
Input: "lintcode", ["lint", "code"]
Output: true
Example 2:
Input: "a", ["a"]
Output: true
思路：
f[i] 表示前i个字符是否可以分。
从前往后枚举结尾。对于每个结尾枚举分成的最后一段的长度j。然后看f[i-j]是否可分。
先看前面i-j个字符是否可分，可分就继续看i-j到i个字符是否可分，可分就认为f[i]个字符可分，如果i-j:i不可分或者i-j不可分，就继续往前挪一位看是否可分，只要找到满足条件的一个就证明f[i]是可分的，可以去看i+1个，用了动态规划来简化整个过程，正着看的过程中再倒着找，挺难想到的，还有一个优化是用字典中最长的key作为取字母长度的上限。
代码：
网友评论