LeetCode 139? 單詞拆分

---

基本還是完全背包的思路，不過用了三重循環，第三重循環是用于判斷當前字符串尾部指定長度字符是否和列表中某一字符串相同，是的話可以將當前dp[j]或上當前下標減去該單詞長度后的下標值。

代碼如下：

class Solution {public boolean wordBreak(String s, List<String> wordDict) {int[] dp = new int[s.length() + 1];dp[0] = 1;for (int i = 0; i <= s.length(); i++) {for (int j = 0; j < wordDict.size(); j++) {if (i >= wordDict.get(j).length()) {int flag = 1;for (int k = 0; k < wordDict.get(j).length(); k++) {if (s.charAt(i - wordDict.get(j).length() + k) != (wordDict.get(j).charAt(k)))flag = 0;}if (flag == 1) dp[i] |= dp[i - wordDict.get(j).length()];}}}return dp[s.length()] == 1;}
}