LintCode第107题-单词拆分
描述
给定字符串 s 和单词字典 dict，判断是否可以利用字典 dict 中的出现的单词拼接出 s，其中字典 dict 中的单词可以重复使用。
因为我们已经使用了更强大的数据，所以普通的DFS方法无法解决此题。
样例 1：
输入：
s = "lintcode"
dict = ["lint", "code"]输出：
true解释：
lintcode可以分成lint和code。
样例 2：
输入：
s = "a"
dict = ["a"]输出：
true解释：
a在dict中。
思路:我们可以考虑动态规划 因为符合这三个条件
| 有“最优子结构” | 整个字符串 s[0...i] 的结果，取决于前面的某些部分是否能由字典拼出 |
| 有“重叠子问题” | 每次都要判断 s[j...i] 是否在字典里、是否可拼接，多个子问题重复判断 |
| 有“状态转移方程” | dp[i] = dp[j] && dict.contains(s[j...i])，这是一个明确的转移逻辑 |
常见的错误有:
boolean[] dp = new boolean[s.length()];
实际上要写上
boolean[] dp = new boolean[s.length()+1];
dp[i] 表示字符串的前 i 个字符 s[0...i-1] 能不能被拼出.
所以我们需要从 dp[0]（空串） 一直到 dp[s.length()]（完整串）
所以：我们必须开一个大小为 s.length() + 1 的数组
举一个具体的示例:
初始化
boolean[] dp = new boolean[9]; // 因为 s.length() == 8
dp[0] = true;
状态转移过程（从 i=1 到 i=8）
i = 1
-
j=0: dp[0]=true，s[0:1] = "l"，不在 dict →
dp[1] = false
i = 2
-
j=0: dp[0]=true，s[0:2] = "li"
-
j=1: dp[1]=false 跳过
→dp[2] = false
i = 3
-
j=0: dp[0]=true，s[0:3] = "lin"
-
j=1: dp[1]=false
-
j=2: dp[2]=false
→dp[3] = false
i = 4
-
j=0: dp[0]=true，s[0:4] = "lint"
→dp[4] = true
i = 5
-
j=0: dp[0]=true，s[0:5] = "lintc"
-
j=1~4: 都不行
→dp[5] = false
i = 6
-
s[0:6] = "lintco" → 不行
-
j=0~5 都不满足条件
→dp[6] = false
i = 7
-
s[0:7] = "lintcod" → 不行
-
j=0~6 都不行
→dp[7] = false
i = 8
我们试一下所有 j：
-
j=0: s[0:8] = "lintcode"，不在 dict（整串不是）
-
j=1~3：都不行
-
j=4: dp[4]=true, s[4:8] = "code"
→dp[8] = true
代码如下:
public class Solution {
/**
* @param s: A string
* @param wordSet: A dictionary of words dict
* @return: A boolean
*/
public boolean wordBreak(String s, Set<String> wordSet) {
// 动态规划数组，表示s的每个前缀是否可以由字典中的单词拼接得到
boolean[] dp=new boolean[s.length()+1];
dp[0]=true;//空字符串是可以拼接的
for(int i=1;i<=s.length();i++)
{
for(int j=0;j<i;j++)
{
if (dp[j]&&wordSet.contains(s.substring(j,i))) {
dp[i]=true;
}
}
}
return dp[s.length()];//返回最终结果
}
}