leetcode 140. Word Break II | 140. 单词拆分 II（动态规划）-蒲公英云

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

题目

https://leetcode.com/problems/word-break-ii/
在这里插入图片描述

题解

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

在这里插入图片描述

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