Question

Formatted question description: https://leetcode.ca/all/140.html

Given a string s and a dictionary of strings wordDict, add spaces in s to construct a sentence where each word is a valid dictionary word. Return all such possible sentences in any order.

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

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: []

Constraints:

1 <= s.length <= 20
1 <= wordDict.length <= 1000
1 <= wordDict[i].length <= 10
s and wordDict[i] consist of only lowercase English letters.
All the strings of wordDict are unique.
Input is generated in a way that the length of the answer doesn't exceed 10⁵.

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

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);
            }
        }
    }

}

############

class Trie {
    Trie[] children = new Trie[26];
    boolean isEnd;

    void insert(String word) {
        Trie node = this;
        for (char c : word.toCharArray()) {
            c -= 'a';
            if (node.children[c] == null) {
                node.children[c] = new Trie();
            }
            node = node.children[c];
        }
        node.isEnd = true;
    }

    boolean search(String word) {
        Trie node = this;
        for (char c : word.toCharArray()) {
            c -= 'a';
            if (node.children[c] == null) {
                return false;
            }
            node = node.children[c];
        }
        return node.isEnd;
    }
}

class Solution {
    private Trie trie = new Trie();

    public List<String> wordBreak(String s, List<String> wordDict) {
        for (String w : wordDict) {
            trie.insert(w);
        }
        List<List<String>> res = dfs(s);
        return res.stream().map(e -> String.join(" ", e)).collect(Collectors.toList());
    }

    private List<List<String>> dfs(String s) {
        List<List<String>> res = new ArrayList<>();
        if ("".equals(s)) {
            res.add(new ArrayList<>());
            return res;
        }
        for (int i = 1; i <= s.length(); ++i) {
            if (trie.search(s.substring(0, i))) {
                for (List<String> v : dfs(s.substring(i))) {
                    v.add(0, s.substring(0, i));
                    res.add(v);
                }
            }
        }
        return res;
    }
}

// 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 Trie:
    def __init__(self):
        self.children = [None] * 26
        self.is_end = False

    def insert(self, word):
        node = self
        for c in word:
            idx = ord(c) - ord('a')
            if node.children[idx] is None:
                node.children[idx] = Trie()
            node = node.children[idx]
        node.is_end = True

    def search(self, word):
        node = self
        for c in word:
            idx = ord(c) - ord('a')
            if node.children[idx] is None:
                return False
            node = node.children[idx]
        return node.is_end


class Solution:
    def wordBreak(self, s: str, wordDict: List[str]) -> List[str]:
        def dfs(s):
            if not s:
                return [[]]
            res = []
            for i in range(1, len(s) + 1): # starts from 1, i is excluded in s[:i]
                if trie.search(s[:i]):
                    # if below dfs() returns empty, then returned res also empty
                    for v in dfs(s[i:]):
                        res.append([s[:i]] + v) # [1] + [2,3] ==> [1, 2, 3]
            return res

        trie = Trie()
        for w in wordDict:
            trie.insert(w)
        ans = dfs(s)
        return [' '.join(v) for v in ans]

#############

class Solution:
    def wordBreak(self, s, wordDict):
        """
        :type s: str
        :type wordDict: Set[str]
        :rtype: List[str]
        """
        res = []
        if not self.check_word_break(s, wordDict):
            return res

        queue = [(0, "")]
        slen = len(s)
        len_list = set(len(w) for w in wordDict)

        while queue:
            tmp_queue = []
            for q in queue:
                start, path = q
                for l in len_list:
                    if start + l <= slen and s[start:start + l] in wordDict:
                        new_node = (start + l, path + " " + s[start:start + l] if path else s[start:start + l])
                        tmp_queue.append(new_node)
                        if start + l == slen:
                            res.append(new_node[1])
            queue = tmp_queue

        return res

    def check_word_break(self, s, wordDict):
        """
        :type s: str
        :type wordDict: Set[str]
        :rtype: bool
        """
        queue = [0]
        slen = len(s)
        len_list = set(len(w) for w in wordDict)
        visited = [0 for _ in range(slen + 1)]

        while queue:
            tmp_queue = []
            for start in queue:
                for l in len_list:
                    if s[start:start + l] in wordDict:
                        if start + l == slen:
                            return True
                        if not visited[start + l]:
                            tmp_queue.append(start + l)
                            visited[start + l] = 1
            queue = tmp_queue

type Trie struct {
	children [26]*Trie
	isEnd    bool
}

func newTrie() *Trie {
	return &Trie{}
}
func (this *Trie) insert(word string) {
	node := this
	for _, c := range word {
		c -= 'a'
		if node.children[c] == nil {
			node.children[c] = newTrie()
		}
		node = node.children[c]
	}
	node.isEnd = true
}
func (this *Trie) search(word string) bool {
	node := this
	for _, c := range word {
		c -= 'a'
		if node.children[c] == nil {
			return false
		}
		node = node.children[c]
	}
	return node.isEnd
}

func wordBreak(s string, wordDict []string) []string {
	trie := newTrie()
	for _, w := range wordDict {
		trie.insert(w)
	}
	var dfs func(string) [][]string
	dfs = func(s string) [][]string {
		res := [][]string{}
		if len(s) == 0 {
			res = append(res, []string{})
			return res
		}
		for i := 1; i <= len(s); i++ {
			if trie.search(s[:i]) {
				for _, v := range dfs(s[i:]) {
					v = append([]string{s[:i]}, v...)
					res = append(res, v)
				}
			}
		}
		return res
	}
	res := dfs(s)
	ans := []string{}
	for _, v := range res {
		ans = append(ans, strings.Join(v, " "))
	}
	return ans
}

using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;

class Node
{
    public int Index1 { get; set; }
    public int Index2 { get; set; }
}

public class Solution {
    public IList<string> WordBreak(string s, IList<string> wordDict) {
        var paths = new List<Tuple<int, string>>[s.Length + 1];
        paths[s.Length] = new List<Tuple<int, string>> { Tuple.Create(-1, (string)null) };
        var wordDictGroup = wordDict.GroupBy(word => word.Length);
        for (var i = s.Length - 1; i >= 0; --i)
        {
            paths[i] = new List<Tuple<int, string>>();
            foreach (var wordGroup in wordDictGroup)
            {
                var wordLength = wordGroup.Key;
                if (i + wordLength <= s.Length && paths[i + wordLength].Count > 0)
                {
                    foreach (var word in wordGroup)
                    {
                        if (s.Substring(i, wordLength) == word)
                        {
                            paths[i].Add(Tuple.Create(i + wordLength, word));
                        }
                    }
                }
            }
        }

        return GenerateResults(paths);
    }

    private IList<string> GenerateResults(List<Tuple<int, string>>[] paths)
    {
        var results = new List<string>();
        var sb = new StringBuilder();
        var stack = new Stack<Node>();
        stack.Push(new Node());
        while (stack.Count > 0)
        {
            var node = stack.Peek();
            if (node.Index1 == paths.Length - 1 || node.Index2 == paths[node.Index1].Count)
            {
                if (node.Index1 == paths.Length - 1)
                {
                    results.Add(sb.ToString());
                }
                stack.Pop();
                if (stack.Count > 0)
                {
                    var parent = stack.Peek();
                    var length = paths[parent.Index1][parent.Index2 - 1].Item2.Length;
                    if (length < sb.Length) ++length;
                    sb.Remove(sb.Length - length, length);
                }
            }
            else
            {
                var newNode = new Node { Index1 = paths[node.Index1][node.Index2].Item1, Index2 = 0 };
                if (sb.Length != 0)
                {
                    sb.Append(' ');
                }
                sb.Append(paths[node.Index1][node.Index2].Item2);
                stack.Push(newNode);
                ++node.Index2;
            }
        }
        return results;
    }
}

140 - Word Break II

Question

Algorithm

Code

All Problems

All Solutions

Welcome to Subscribe On Youtube

Question

Algorithm

Code

All Problems

All Solutions