leetcode 140. Word Break II 动态规划 存储路径

题意

Given a non-empty string s and a dictionary wordDict containing a list of non-empty words, add spaces in s to construct a sentence where each word is a valid dictionary word. Return all such possible sentences.

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题，解法不变，boolean[]改成Map<Integer, List<Integer>> // 从保存是否可分割，改为了null表示不可分割，list（非null表示可分割）存前一个分割点 // Runtime: 7 ms, faster than 73.92% of Java online submissions for Word Break II. //Memory Usage: 39.2 MB, less than 7.85% of Java online submissions for Word Break II. public List<String> wordBreak(String s, List<String> wordDict) { Map<Integer, List<String>> sizedWordDict = new HashMap<>(); for (String word : wordDict) { List<String> words = sizedWordDict.computeIfAbsent(word.length(), k -> new ArrayList<>()); words.add(word); } Map<Integer, List<Integer>> indexes = new HashMap<>(); indexes.put(0, new ArrayList<>()); for (int i = 1; i <= s.length(); i++) { for (int k = 0; k < i; k++) { if (indexes.get(k) != null) { List<String> words = sizedWordDict.get(i - k); if (words != null && words.contains(s.substring(k, i))) { List<Integer> idxes = indexes.computeIfAbsent(i, n -> new ArrayList<>()); idxes.add(k); } } } } List<String> rst = new ArrayList<>(); if (indexes.get(s.length()) != null) dfs(rst, s, indexes, s.length(), new ArrayList<>()); return rst; } private void dfs(List<String> rst, String s, Map<Integer, List<Integer>> indexes, int idx, ArrayList<String> strings) { if (idx == 0) rst.add(buildString(strings)); for (Integer i : indexes.get(idx)) { strings.add(0, s.substring(i, idx)); dfs(rst,s, indexes, i, strings); strings.remove(0); } } private String buildString(ArrayList<String> strings) { StringBuilder sb = new StringBuilder(); for (int i = 0; i < strings.size(); i++) { if (i != 0) sb.append(' '); sb.append(strings.get(i)); } return sb.toString(); }