140.Word Break II

Tags: [backtracking], [DFS], [DP], [memo]

Com: {t}

Hard: [###]

Link: https://leetcode.com/problems/word-break-ii/\#/description

Given a non-empty string sand 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. You may assume the dictionary does not contain duplicate words.

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"].

UPDATE (2017/1/4):
The wordDict parameter had been changed to a list of strings (instead of a set of strings). Please reload the code definition to get the latest changes.

Solution: DSF, Backtracking, DP, Memo

public class Solution {
    public List<String> wordBreak(String s, List<String> wordDict) {
        if (s == null || s.length() == 0 || wordDict == null || wordDict.size() == 0) {
            return new ArrayList<>();
        }

        Set<String> dict = new HashSet<>(wordDict);
        Map<String, List<String>> memo = new HashMap<>();
        List<String> rest = wordBreakHelper(s, dict, memo);
        return rest != null ? rest : new ArrayList<>();
    }

    private List<String> wordBreakHelper(String s, Set<String> dict, Map<String, List<String>> memo) {
        if (memo.containsKey(s)) {
            return memo.get(s);
        }

        // base case.
        if (s.length() == 0) {
            return new ArrayList<>();
        }

        List<String> rest = new ArrayList<>();
        for (int i = 0; i < s.length(); i ++) {
            String w = s.substring(0, i + 1);
            if (!dict.contains(w)) {
                continue;
            }

            List<String> remainings = wordBreakHelper(s.substring(i + 1, s.length()), dict, memo);
            if (remainings == null) {
                // this means, if we use the current w, finally we cannot process the entire string.
                continue;
            }
            else if (remainings.size() == 0) {
                rest.add(w);
            } else {
                for (String remaining : remainings) {
                    rest.add(String.format("%s %s", w, remaining));
                }                
            }
        }

        if (rest.size() == 0) {
            memo.put(s, null);
            return null;
        }

        memo.put(s, rest);
        return rest;
    }
}

Revelation:

• 第一个想法是DFS + Backtracking，往recursion function中出入 buff 和 rest，能得出正确答案，但是超时。所以我想到可以用DP memo， 但如果用DP memo就要重新定义recursion function的含义，让recursion可以返回值，那么新的recursion的含义就是:给定string s, dict, 返回能做出来的string list. (这种定义，就好像把recursion 变成stateless 的啦). 那么base case就是如果s 是空string那么没什么可以拼的，就返回empty list. Body of recursion：只需要看第一个word在哪里断开，如果这个word不在dict中，那么skip，如果这个word导致 remainings 是null，那么说明用当前cut的word会导致后面进行不完，所以也skip，如果remainings中有东西那么就迭代remainings中string逐个和当前的word进行拼接，如果remainings为空那么就直接把当前word放入rest中（rest中不会有重复）， 最后在for loop结束后，如果rest还是空的，那么说明无法找到一个解，应该return null， 如果rest不为空就return rest， 应为在recursion的最开始已经查过base case了，所以如果这时rest还未空，那就说明当前情况无解.

Note:

• Time complexity = O(n^2), n is the length of the given string, because there are n^2, substring for s, and the worst case, each substring will be memo's key, and each memo cell we only calculate once, so the worst case T = O(n^2).

Time Limited Exceeded: DFS, Backtracking

public class Solution {
    public List<String> wordBreak(String s, List<String> wordDict) {
        if (s == null || s.length() == 0 || wordDict == null || wordDict.size() == 0) {
            return new ArrayList<>();
        }

        List<String> buff = new ArrayList<>();
        List<String> rest = new ArrayList<>();
        Set<String> dict = new HashSet(wordDict);
        wordBreakHelper(s, dict, 0, buff, rest);
        return rest;
    }

    private void wordBreakHelper(String s, Set<String> dict, int index, List<String> buff, List<String> rest) {
        // base case
        if (index >= s.length()) {
            StringBuilder sbuilder = new StringBuilder();
            for (String w : buff) {
                sbuilder.append(w).append(' ');
            }
            if (sbuilder.length() > 0) {
                sbuilder.setLength(sbuilder.length() - 1);
            }
            rest.add(sbuilder.toString());
            return;
        }

        for (int i = index; i < s.length(); i ++) {
            String word = s.substring(index, i + 1);
            if (!dict.contains(word)) {
                continue;
            }

            buff.add(word);
            wordBreakHelper(s, dict, i + 1, buff, rest);
            buff.remove(buff.size() - 1);
        }
    }
}

Note:

• Time complexity = O(n!), n is the length of the given string.