算法训练营第四十九天 | LeetCode 139单词拆分

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;
    }
}