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

140 - Word Break II

Question

Algorithm

Code

All Problems

All Solutions