leetcode 139. Word Break | 139. 单词拆分（动态规划）

大家好，欢迎来到IT知识分享网。

题目

https://leetcode.com/problems/word-break/

题解

时隔一天，再次遇到 dp 问题…
本题和 leetcode 375. Guess Number Higher or Lower II | 375. 猜数字大小 II（动态规划思路总结）的思路是一样的，连 dp 数组的遍历方向都是一样的（斜向）…
这是全局第 5 道没看答案的 dp 问题，所以，dp 到底是不是玄学？…

以下面的测试用例为例，斜向依次填充 dp 数组过程如图所示。

public static void main(String[] args) { 
   
    Solution solution = new Solution();
    List<String> list = new ArrayList<>();
    list.add("cat");
    list.add("cats");
    list.add("and");
    list.add("sand");
    list.add("dog");
    list.add("catsanddog");
    solution.wordBreak("catsanddog", list);
}

class Solution { 
   
    public boolean wordBreak(String s, List<String> wordDict) { 
   
        HashSet<String> dict = new HashSet<>();
        for (String word : wordDict) { 
   
            dict.add(word);
        }
        
        int n = s.length();
        boolean[][] dp = new boolean[n + 1][n + 1];
        for (int i = 1; i <= n; i++) { 
   
            for (int j = i; j <= n; j++) { 
   
                int L = j - i;
                int R = j;
                if (dict.contains(s.substring(L, R))) { 
   
                    dp[L][R] = true;
                } else { 
   
                    for (int M = L + 1; M < R; M++) { 
   
                        // [L...M) + [M...R)
                        if (dp[L][M] & dp[M][R]) { 
   
                            dp[L][R] = true;
                            break;
                        }
                    }
                }
            }
        }
        return dp[0][n];
    }
}