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:

[]

Solution

(1) Java

class Solution {
    public List<String> wordBreak(String s, List<String> wordDict) {
        List<String> rst = new ArrayList<>();
        Map<String, List<String>> cache = new HashMap<>();
        Set<String> wordSet = new HashSet<>();
        wordSet.addAll(wordDict);
        helper(s, wordSet, rst, new ArrayList<String>(), 0, cache);
        return rst;
    }

    private List<String> helper(String s, Set<String> wordSet, List<String> rst, List<String> list, int start, Map<String, List<String>> cache) {
        if (s.length() == start) {
            rst.add(String.join(" ",list));
            return new ArrayList<String>();
        }
        String tailStr = s.substring(start);
        if (cache.containsKey(tailStr)) { 
            List<String> l = cache.get(tailStr);
            for (String str : l) {
                rst.add(String.join(" ",list) + " " + str);
            }
            return l;
        }

        List<String> localRst = new ArrayList<>();
        for (int i = start+1; i <= s.length(); i++) {
            String sub = s.substring(start, i);
            if (wordSet.contains(sub)) {
                list.add(sub);
                List<String> l = helper(s, wordSet, rst, list, i, cache);
                list.remove(list.size()-1);
                if (i == s.length()) {
                    localRst.add(sub);
                } else {
                    for (String str : l) {
                        localRst.add(sub + " " + str);
                    }
                }                
            }
        }
        cache.put(s.substring(start), localRst);
        return localRst;
    }
}

(2) Python

class Solution:
    def wordBreak(self, s, wordDict):
        """
        :type s: str
        :type wordDict: List[str]
        :rtype: List[str]
        """
        def helper(start):
            if start == len(s):
                rst.append(" ".join(path))
                return []
            if s[start:] in mem:
                l = mem[s[start:]]
                for ll in l:
                    rst.append(" ".join(path)+" "+ll)
                return l
            path2 = []
            for i in range(start, len(s)):
                sub = s[start:i+1]
                if sub in wordSet:
                    path.append(sub)
                    ll = helper(i+1)
                    path.pop(len(path)-1)
                    if i == len(s)-1:
                        path2.append(sub)
                    else:
                        for pp in ll:
                            path2.append(sub+" "+pp)
            mem[s[start:]] = path2
            return path2


        if not s or not wordDict:
            return []
        mem = {}
        wordSet = set(wordDict)
        rst = []
        path = []
        helper(0)
        return rst

(3) Scala