Question
Formatted question description: https://leetcode.ca/all/140.html
140 Word Break II
Given a string s and a dictionary of words dict,
add spaces in s to construct a sentence where each word is a valid dictionary word.
Return all such possible sentences.
For example, given
s = "catsanddog",
dict = ["cat", "cats", "and", "sand", "dog"].
A solution is ["cats and dog", "cat sand dog"].
Algorithm
If the memory array
is not used for optimization to reduce repeated calculations, then the recursive
method is no different from brute force, and it will not pass OJ with a high probability. So we have to avoid duplicated counting.
To cache this intermediate result, since we must save s and all of its split strings at the same time, a HashMap
can be used to establish the mapping between the two, then in the recursive function, we first detect the current s whether there is a mapping, if so, return directly.
If s
is empty, an empty string is returned.
Code
Java
-
public class Word_Break_II { public static void main(String[] args) { Word_Break_II out= new Word_Break_II(); Solution_dfs s = out.new Solution_dfs(); Set<String> dict = new HashSet<String>(); dict.add("cat"); dict.add("cats"); dict.add("and"); dict.add("sand"); dict.add("dog"); List<String> r = s.wordBreak("catsanddog", dict); r.stream().forEach(System.out::println); } public class Solution_dfs { Map<String, List<String>> hm = new HashMap<>(); public List<String> wordBreak(String s, Set<String> dict) { if (hm.containsKey(s)) return hm.get(s); // @note: I failed here by "return new Arraylist()", then "for (String rem: remainderList) {" will not initiate if (s.isEmpty()) return Arrays.asList(""); List<String> list = new ArrayList<String>(); for (String each: dict) { if (each.length() > s.length() || !s.substring(0, each.length()).equals(each)) { continue; } List<String> remainderList = wordBreak(s.substring(each.length()), dict); for (String rem: remainderList) { list.add(each + (rem.isEmpty()? "": " ") + rem); } } hm.put(s, list); return list; } } public class Solution { List<String> list = new ArrayList<String>(); public List<String> wordBreak(String s, Set<String> dict) { if (s == null || dict == null || dict.size() == 0) return list; // hashmap, from "index of s", to "previous index" HashMap<Integer, HashSet<Integer>> hm = new HashMap<Integer, HashSet<Integer>>(); int length = s.length(); boolean[] dp = new boolean[length + 1]; dp[0] = true; for (int i = 0; i < length + 1; i++) { if (dp[i] == false) continue; for (String each: dict) { if (i + each.length() > length) continue; if (s.substring(i, i + each.length()).equals(each)) { dp[i + each.length()] = true; // 注意hashmap里放的是index if (hm.containsKey(i + each.length())) { hm.get(i + each.length()).add(i); // start of next word, add current i as previous index } else { HashSet<Integer> st = new HashSet<Integer>(); st.add(i); hm.put(i + each.length(), st); } } } } if (!dp[length]) return list; trackback(hm, s, length, ""); return list; } // 其实可以直接存,不需要多这一个method public void trackback(HashMap<Integer, HashSet<Integer>> hm, String s, int current, String result) { if (current == 0) { result = result.substring(1); list.add(result); } for(int prev: hm.get(current)) { trackback(hm, s, prev, " " + s.substring(prev, current) + result); } } } }
-
// OJ: https://leetcode.com/problems/word-break-ii/ // Time: O(N!) // Space: O(N + D) class Solution { vector<string> ans, tmp; unordered_set<string> st; void dfs(string &s, int i) { if (i == s.size()) { string n; for (auto &t : tmp) { n += (n.size() ? " " : "") + t; } ans.push_back(n); } for (int j = i + 1; j <= s.size(); ++j) { auto sub = s.substr(i, j - i); if (st.count(sub) == 0) continue; tmp.push_back(sub); dfs(s, j); tmp.pop_back(); } } public: vector<string> wordBreak(string s, vector<string>& dict) { st = unordered_set<string>(begin(dict), end(dict)); dfs(s, 0); return ans; } };
-
class Solution(object): def wordBreak(self, s, wordDict): """ :type s: str :type wordDict: Set[str] :rtype: List[str] """ res = [] if not self.checkWordBreak(s, wordDict): return res queue = [(0, "")] slen = len(s) lenList = [l for l in set(map(len, wordDict))] while queue: tmpqueue = [] for q in queue: start, path = q for l in lenList: if start + l <= slen and s[start:start + l] in wordDict: newnode = (start + l, path + " " + s[start:start + l] if path else s[start:start + l]) tmpqueue.append(newnode) if start + l == slen: res.append(newnode[1]) queue, tmpqueue = tmpqueue, [] return res def checkWordBreak(self, s, wordDict): """ :type s: str :type wordDict: Set[str] :rtype: bool """ queue = [0] slen = len(s) lenList = [l for l in set(map(len, wordDict))] visited = [0 for _ in range(0, slen + 1)] while queue: tmpqueue = [] for start in queue: for l in lenList: if s[start:start + l] in wordDict: if start + l == slen: return True if visited[start + l] == 0: tmpqueue.append(start + l) visited[start + l] = 1 queue, tmpqueue = tmpqueue, [] return False