140.WordBreakII

Z时代
2024-01-10
分类：综合

Note:

The same word in the dictionary may be reused multiple times in the segmentation.

You may assume the dictionary does not contain duplicate words.

Example 1:

Input:
s = "catsanddog"
wordDict = ["cat", "cats", "and", "sand", "dog"]
Output:
[
  "cats and dog",
  "cat sand dog"
]

Example 2:

Input:

s = "pineapplepenapple"

wordDict = ["apple", "pen", "applepen", "pine", "pineapple"]

Output:

[

"pine apple pen apple",

"pineapple pen apple",

"pine applepen apple"

]

Explanation: Note that you are allowed to reuse a dictionary word.

Example 3:

Input:
s = "catsandog"
wordDict = ["cats", "dog", "sand", "and", "cat"]
Output:
[]

解题思路

这道题的解法其实跟139. Word Break一样，可以参考139. Word Break的思路 https://my.oschina.net/JiamingMai/blog/4331735 ，与139. Word Break稍有不同的是，这道题需要在此基础上将h[0][i]为true的所有情况记录起来。

时间复杂度分析

本质与139. Word Break一样，所以时间复杂度也是O(kn^2)，分析过程参考 https://my.oschina.net/JiamingMai/blog/4331735

最终实现

Java 实现

public class Solution {
    List<String>[] records;
    private boolean[][] h;
    private boolean[][] r;
    public List<String> wordBreak(String s, List<String> wordDict) {
        int n = s.length();
        if (!fastWordBreakInternal(s, wordDict)) {
            return new ArrayList<>();
        }
        boolean res = wordBreakInternal(s, wordDict);
        if (res) {
            return records[n];
        }
        return new ArrayList<>();
    }
    public boolean fastWordBreakInternal(String s, List<String> wordDict) {
        int n = s.length();
        h = new boolean[n+1][n+1];
        r = new boolean[n+1][n+1];
        initR(n, s, wordDict);
        h[0][0] = true;
        for (int i = 1; i <= n; i++) {
            for (int j = i; j >= 0; j--) {
                if (!h[0][i]) {
                    h[0][i] = h[0][i-j] && r[i-j][i];
                } else {
                    break;
                }
            }
        }
        return h[0][n];
    }
    public boolean wordBreakInternal(String s, List<String> wordDict) {
        int n = s.length();
        h = new boolean[n + 1][n + 1];
        r = new boolean[n + 1][n + 1];
        records = new List[n + 1];
        initR(n, s, wordDict);
        h[0][0] = true;
        for (int i = 1; i <= n; i++) {
            for (int j = i; j >= 0; j--) {
                if (h[0][i - j] && r[i - j][i]) {
                    h[0][i] = true;
                    record(i, j, s);
                }
            }
        }
        return h[0][n];
    }
    private void record(int i, int j, String s) {
        if (null == records[i]) {
            records[i] = new ArrayList<>();
        }
        String token = s.substring(i - j, i);
        if (null != records[i - j]) {
            for (String str : records[i - j]) {
                StringBuffer sb = new StringBuffer();
                sb.append(str).append(" ").append(token);
                records[i].add(sb.toString());
            }
        }  else {
            records[i].add(token);
        }
    }
    private void initR(int n, String s, List<String> wordDict) {
        for (int i = 0; i <= n; i++) {
            for (int j = i; j <= n; j++) {
                r[i][j] = r(i, j, s, wordDict);
            }
        }
    }
    private boolean r(int i, int j, String s, List<String> wordDict) {
        String token = s.substring(i, j);
        for (String word : wordDict) {
            if (word.equals(token)) {
                return true;
            }
        }
        return false;
    }
    public static void main(String[] args) {
        List<String> wordDict = new ArrayList<>();
        wordDict.add("a");
        wordDict.add("aa");
        wordDict.add("aaa");
        wordDict.add("aaaa");
        wordDict.add("aaaaa");
        wordDict.add("aaaaaa");
        wordDict.add("aaaaaaa");
        wordDict.add("aaaaaaaa");
        wordDict.add("aaaaaaaaa");
        wordDict.add("aaaaaaaaaa");
        String s = "aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaabaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaa";
        Solution solution = new Solution();
        List<String> res = solution.wordBreak(s, wordDict);
        res.stream().forEach(str -> {System.out.println(str);});
    }
}