Java|Java 算法 - 单词拆分I(动态规划) Java算法-单词拆分I(动态规划

??刚刚楼主做了一道关于动态规划的题，这道题其实不是很难，就是比较坑。
题意：

给出一个字符串s和一个词典，判断字符串s是否可以被空格切分成一个或多个出现在字典中的单词。

样例：

给出s = "lintcode"dict = ["lint","code"]返回 true 因为"lintcode"可以被空格切分成"lint code"

1.n^2的解法(超时) (1).解题思路
??这道题有两种方式来解决问题，一种方式的时间复杂度是n^2,一种是方式的时间复杂度是nk。
??我们先来看看n^2的解法。
??这道题其实一道典型的动态规划，而n^2的解法就是使用动态规划。
??第一步，首先，我们先定义一个一维数组dp,长度为string.length + 1,默认dp[0] = true，dp[i]表示的意思就是，string字符串0~i的子串是否能够符合要求;
??第二步，然后进行一次二重循环，第一重表示截取子串的起点，第二重表示截取子串的终点，如果当前截取的子串字典中出现过，那么dp[j] = dp[i] && dict.contains(s.substring(i, j))。
(2).代码

public boolean wordBreak(String s, Set dict) { boolean[] dp = new boolean[s.length() + 1]; int minLength = getMinLength(dict); dp[0] = true; for (int i = 0; i < s.length(); i++) { if (!dp[i]) { continue; } for (int j = i + 1; j <= s.length(); j++) { //如果剩下的字符串的长度小于字典中最短字符串的长度 //直接跳出 if (s.length() - i < minLength) { break; } //如果dp[j]为true，那么不能被重置 //这是为了避免如果当前的dp[j]为true，但是在后面被重置为false //例如codecode1,如果在这里的dp[4] = true(dict为["code", "code1"]) //但是后面dp[4]会被重置为false if (!dp[j]) { dp[j] = dp[i] && dict.contains(s.substring(i, j)); }} } return dp[s.length()]; }private int getMinLength(Set dict) { int min = Integer.MAX_VALUE; for (String string : dict) { min = Math.min(min, string.length()); } return min; }

2.nk的解法 (1).解题思路
【Java|Java 算法 - 单词拆分I(动态规划)】??nk的解法相较于n^2的解法，它的第二重循环遍历的是字典，而不是字符串。这里就不详细的解释，可以看代码理解理解。

public boolean wordBreak(String s, Set dict) {boolean[] dp = new boolean[s.length() + 1]; dp[0] = true; for (int i = 0; i < s.length(); i++) { if(!dp[i]){ continue; } for (String str : dict) { if (i + str.length() <= s.length() && s.substring(i, i + str.length()).equals(str)) dp[i + str.length()] = true; } } return dp[s.length()]; }