[数据结构与算法]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;
    }
}