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

Understand the Problem:
The problem asks for partition a string such that each part is included in the dictionary. In addition, you are asked for returning all possible sentences. The mainly difference between work break I is, in that question you are only required to return if such a partition existed. In this problem, however, you need to return all possible sentences. 

Recursive Solution:
We first consider the recursive solution. The recursive solution is very similar to the work break I, the mainly difference is we save all intermediate results.

Code (Java):

public class Solution {
    public ArrayList<String> wordBreak(String s, Set<String> dict) {
        ArrayList<String> result = new ArrayList<String>();
        if (s == null || s.isEmpty() || dict.isEmpty()) 
            return result;
        
        wordBreakHelper(s, dict, "", result);
        
        return result;
    }
    
    private void wordBreakHelper(String s, Set<String> dict, String item, ArrayList<String> result) {
        if (s.isEmpty()) {
            result.add(item);
            return;
        }
        
        StringBuilder sb = new StringBuilder();
        for (int i = 0; i < s.length(); i++) {
            sb.append(s.charAt(i));
            if (dict.contains(sb.toString())) {
                String newItem = item.length() > 0 ? item + " " + sb.toString() : sb.toString();
                wordBreakHelper(s.substring(i + 1), dict, newItem, result);
            }
        }
    }
}

Discussion:
The time complexity is still O(2^n), because we partitioned the string into two substrings and recursively solve the problem. Not surprisingly, it got TLE error at OJ.

An Accepted Solution:
The previous solution exceeds the time limits of OJ is because there is a test case containing very long string which is not breakable. So one solution is for each recursion, we check if the string is breakable at first, using the method in Word Break I. If not, we don't need to do the following computations. 

Code (Java):

public class Solution {
    public ArrayList<String> wordBreak(String s, Set<String> dict) {
        ArrayList<String> result = new ArrayList<String>();
        if (s == null || s.isEmpty() || dict.isEmpty()) 
            return result;
        
        wordBreakHelper(s, dict, "", result);
        
        return result;
    }
    
    private void wordBreakHelper(String s, Set<String> dict, String item, ArrayList<String> result) {
        if (!isBreakable(s, dict)) return;
        
        if (s.isEmpty()) {
            result.add(item);
            return;
        }
        
        StringBuilder sb = new StringBuilder();
        for (int i = 0; i < s.length(); i++) {
            sb.append(s.charAt(i));
            if (dict.contains(sb.toString())) {
                String newItem = item.length() > 0 ? item + " " + sb.toString() : sb.toString();
                wordBreakHelper(s.substring(i + 1), dict, newItem, result);
            }
        }
    }
    
    private boolean isBreakable(String s, Set<String> dict) {
        boolean[] dp = new boolean[s.length() + 1];
        dp[0] = true;
        
        for (int i = 1; i <= s.length(); i++) {
            for (int j = 0; j < i; j++) {
                if (dp[j] == true && dict.contains(s.substring(j, i))) {
                    dp[i] = true;
                    break;
                }
            }
        }
        
        return dp[s.length()];
    }
}

Update on 11/10/14:

import java.util.*;

public class Solution {
    public List<String> wordBreak(String s, Set<String> dict) {
        List<String> result = new ArrayList<String>();
        
        if (s == null || s.length() == 0 || dict == null || dict.size() == 0) {
            return result;
        }
        
        List<String> curr = new ArrayList<String>();
        wordBreakHelper(0, s, dict, curr, result);
        
        return result;
    }
    
    private void wordBreakHelper(int start, String s, Set<String> dict, List<String> curr, List<String> result) {
        if (start >= s.length()) {
            String temp = constructString(curr);
            result.add(temp);
        }
        
        for (int i = start; i < s.length(); i++) {
            if (dict.contains(s.substring(start, i + 1))) {
                curr.add(s.substring(start, i + 1));
                wordBreakHelper(i + 1, s, dict, curr, result);
                curr.remove(curr.size() - 1);
            }
        }
    }
    
    private String constructString(List<String> tokens) {
        StringBuilder sb = new StringBuilder();
        
        for (int i = 0; i < tokens.size() - 1; i++) {
            sb.append(tokens.get(i) + " ");
        }
        
        sb.append(tokens.get(tokens.size() - 1));
        
        return sb.toString();
    }

    public static void main(String[] args) {
      Solution sol = new Solution();

      String s = "catsanddog";
      Set<String> dict = new HashSet<String>();
      dict.add("cat");
      dict.add("cats");
      dict.add("and");
      dict.add("sand");
      dict.add("dog");

      List<String> result = sol.wordBreak(s, dict);

      for (String str : result) {
        System.out.println("Result is " + str);
      }
    }
}

Update on 5/2/19: Memorization
The reason to use memo is think of one example
lint code
li nt code
l int code

dict = lint, li, nt, l, int 
So we check the "code" repeatedly whereas it is not in the dict.

public class Solution {
    /*
     * @param s: A string
     * @param wordDict: A set of words.
     * @return: All possible sentences.
     */
    public List<String> wordBreak(String s, Set<String> wordDict) {
        // write your code here
        if (s == null || s.length() == 0 || wordDict == null || wordDict.size() == 0) {
            return new ArrayList<String>();
        }

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

        List<String> ans = new ArrayList<>();

        if (wordDict.contains(s)) {
            ans.add(s);
        }

        for (int i = 1; i <= s.length(); i++) {
            String prefix = s.substring(0, i);
            if (wordDict.contains(prefix)) {
                String suffix = s.substring(i);
                
                List<String> suffixAns = wordBreakHelper(suffix, wordDict, memo);
                
                for (String word : suffixAns) {
                    ans.add(prefix + " " + word);
                }
            }
        }

        memo.put(s, ans);

        return ans;
    }
}