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

你的名字 2022-08-31 09:55 164阅读 0赞

## 题目 ##

[https://leetcode.com/problems/word-break/][https_leetcode.com_problems_word-break]  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3NpbmF0XzQyNDgzMzQx_size_1_color_FFFFFF_t_70]

## 题解 ##

时隔一天，再次遇到 dp 问题…  
本题和 [leetcode 375. Guess Number Higher or Lower II | 375. 猜数字大小 II（动态规划思路总结）][leetcode 375. Guess Number Higher or Lower II _ 375. _ II]的思路是一样的，连 dp 数组的遍历方向都是一样的（斜向）…  
这是全局第 5 道没看答案的 dp 问题，所以，dp 到底是不是玄学？…  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3NpbmF0XzQyNDgzMzQx_size_1_color_FFFFFF_t_70 1]  
以下面的测试用例为例，斜向依次填充 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);
    }

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3NpbmF0XzQyNDgzMzQx_size_1_color_FFFFFF_t_70 2]

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

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3NpbmF0XzQyNDgzMzQx_size_16_color_FFFFFF_t_70]

[https_leetcode.com_problems_word-break]: https://leetcode.com/problems/word-break/
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3NpbmF0XzQyNDgzMzQx_size_1_color_FFFFFF_t_70]: /images/20220829/dce9abfb937f48a0828721830b6bc5a8.png
[leetcode 375. Guess Number Higher or Lower II _ 375. _ II]: https://hanquan.blog.csdn.net/article/details/118996254
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3NpbmF0XzQyNDgzMzQx_size_1_color_FFFFFF_t_70 1]: /images/20220829/3c4bf2f725dd48e5a472de1ec0c1d836.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3NpbmF0XzQyNDgzMzQx_size_1_color_FFFFFF_t_70 2]: /images/20220829/c9ac5241a86b49519b2deb4acbe3d9e5.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3NpbmF0XzQyNDgzMzQx_size_16_color_FFFFFF_t_70]: /images/20220829/313f07e6ce8d44d18bcec6b903afef27.png