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

朴灿烈づ我的快乐病毒、 2022-08-31 11:05 153阅读 0赞

## 题目 ##

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

## 题解 ##

由 [leetcode 139. Word Break | 139. 单词拆分（动态规划）][leetcode 139. Word Break _ 139.] 改造而来。  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3NpbmF0XzQyNDgzMzQx_size_16_color_FFFFFF_t_70 1]  
dp 过程示例:

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

class Solution { 
        public List<String> wordBreak(String s, List<String> wordDict) { 
            HashSet<String> dict = new HashSet<>();
            for (String word : wordDict) { 
                dict.add(word);
            }
    
            int n = s.length();
            ArrayList<int[]>[][] dp = new ArrayList[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;
                    dp[L][R] = new ArrayList<>();
                    if (dict.contains(s.substring(L, R))) { 
                        ArrayList<int[]> t = new ArrayList<>();
                        t.add(new int[]{ L, R});
                        dp[L][R] = t;
                    }
                    for (int M = L + 1; M < R; M++) { 
                        // [L...M) + [M...R)
                        if (dp[L][M] != null && dp[L][M].size() > 0 && dp[M][R] != null && dp[M][R].size() > 0) { 
                            dp[L][R].add(new int[]{ L, M});
                            dp[L][R].add(new int[]{ M, R});
                        }
                    }
                }
            }
            Set<String> res = join(dp, 0, n, s);
            return new ArrayList<>(res);
        }
    
        public Set<String> join(ArrayList<int[]>[][] dp, int L, int R, String s) { 
            ArrayList<int[]> pair = dp[L][R];
            Set<String> res = new HashSet<>();
            int i = 0;
            if (pair.size() % 2 == 1) { 
                res.add(s.substring(L, R));
                i = 1;
            }
            for (; i + 1 < pair.size(); i += 2) { 
                Set<String> lSet = join(dp, L, pair.get(i)[1], s);
                Set<String> rSet = join(dp, pair.get(i + 1)[0], R, s);
                for (String l : lSet) { 
                    for (String r : rSet) { 
                        res.add(l + " " + r);
                    }
                }
            }
            return res;
        }
    }

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

[https_leetcode.com_problems_word-break-ii]: https://leetcode.com/problems/word-break-ii/
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3NpbmF0XzQyNDgzMzQx_size_16_color_FFFFFF_t_70]: /images/20220829/366062d4ee1444d7b97db8f3f6e2410e.png
[leetcode 139. Word Break _ 139.]: https://hanquan.blog.csdn.net/article/details/119056361
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3NpbmF0XzQyNDgzMzQx_size_16_color_FFFFFF_t_70 1]: /images/20220829/c7a835ebd06e480a9134c66bbb49d2d3.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3NpbmF0XzQyNDgzMzQx_size_16_color_FFFFFF_t_70 2]: /images/20220829/b9e0f6b867ba445a870816400438eaff.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3NpbmF0XzQyNDgzMzQx_size_16_color_FFFFFF_t_70 3]: /images/20220829/1951c4fc459c4702bd6be3b5bf00ed0e.png