Word Break II

Given a string A and a dictionary of words B, add spaces in A to construct a sentence where each word is a valid dictionary word.

Return all such possible sentences.

Note : Make sure the strings are sorted in your result.

Input Format:

The first argument is a string, A.
The second argument is an array of strings, B.
Output Format:

Return a vector of strings representing the answer as described in the problem statement.
Constraints:

1 <= len(A) <= 50
1 <= len(B) <= 25
1 <= len(B[i]) <= 20
Examples:

Input 1:
    A = "b"
    B = ["aabbb"]

Output 1:
    []

Input 1:
    A = "catsanddog",
    B = ["cat", "cats", "and", "sand", "dog"]

Output 1:
    ["cat sand dog", "cats and dog"]

Solution:

Time: O(n^n)
Space: O(n^2)

public class Solution {
    public ArrayList<String> wordBreak(String A, ArrayList<String> B) {
        ArrayList<String> result = new ArrayList<>();
        Set<String> dict = new HashSet<>(B);
        ArrayList<String> curr = new ArrayList<>();
        backtrack(A, dict, curr, result);
        Collections.sort(result);
        return result;
    }
    
    private void backtrack(String A, Set<String> dict, ArrayList<String> curr, ArrayList<String> result) {
        if (A.length() == 0) {
            StringBuilder sb = new StringBuilder();
            for (int i = 0; i < curr.size(); i ++) {
                if (i != 0) sb.append(" ");
                sb.append(curr.get(i));
            }
            result.add(sb.toString());
            return;
        }
        for (int i = 1; i <= A.length(); i ++) {
            String sub = A.substring(0, i);
            if (dict.contains(sub)) {
                curr.add(sub);
                backtrack(A.substring(i, A.length()), dict, curr, result);
                curr.remove(curr.size() - 1);
            }
        }
    }
}

Solution2:

Time: O(n^3)
Space: O(n^2)

public class Solution {
    public ArrayList<String> wordBreak(String A, ArrayList<String> B) {
        Set<String> dict = new HashSet<>(B);
        Map<Integer, ArrayList<String>> map = new HashMap<>();
        ArrayList<String> result = dfs(A, dict, map, 0);
        Collections.sort(result);
        return result;
    }
    
    private ArrayList<String> dfs(String A, Set<String> dict, Map<Integer, ArrayList<String>> map, int start) {
        if (map.containsKey(start)) {
            return map.get(start);
        }
        ArrayList<String> res = new ArrayList<>();
        if (start == A.length()) {
            res.add("");
        }

        for (int end = start + 1; end <= A.length(); end ++) {
            String sub = A.substring(start, end);
            if (dict.contains(sub)) {
                ArrayList<String> rest = dfs(A, dict, map, end);
                for (String l : rest) {
                    res.add(A.substring(start, end) + (l.equals("") ? "" : " ") + l);
                }
            }
        }
        map.put(start, res);
        return res;
    }
}

class Solution {
    public List<String> wordBreak(String s, List<String> wordDict) {
        Set<String> set = new HashSet(wordDict);
        Map<Integer, List<String>> memo = new HashMap();
        List<String> result = dfs(s, set, memo, 0);
        return result;
    }
    
    private List<String> dfs(String s, Set<String> set, Map<Integer, List<String>> memo, int start) {
        if (memo.containsKey(start)) {
            return memo.get(start);
        }
        List<String> result = new ArrayList<>();
        if (start == s.length()) {
            result.add("");
            return result;
        }
        for (int end = start + 1; end <= s.length(); end ++) {
            String sub = s.substring(start, end);
            if (set.contains(sub)) {
                List<String> rest = dfs(s, set, memo, end);
                for (String r : rest) {
                    result.add(sub + (r.isEmpty() ? "" : " " + r));
                }
            }
        }
        memo.put(start, result);
        return result;
    }
}