0140. Word Break II

https://leetcode.com/problems/word-break-ii

Description

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.

ac1: DFS with memorization

Complexity: worst case is O(2^n), e.g. input "aaaaaa", with wordDict = ["a", "aa", "aaa", "aaaa", "aaaaa", "aaaaa"]. Every possible partition is a valid sentence, and there are 2^n-1 such partitions.

With cache, the runtime improves from O(2^n) to O(n^2), e.g. "aaaaab", with wordDict = ["a", "aa", "aaa", "aaaa", "aaaaa", "aaaaa"]. Why O(n^2)? Think reversely, it's just like finding valid partitions like O(n^2) DP in 0139. Word Break.

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

        Set<String> dict = new HashSet<String>(wordDict);
        Map<Integer,List<String>> map = new HashMap<Integer,List<String>>();
        return dfs(s, 0, dict, map);
    }

    private List<String> dfs(String s, int start, Set<String> dict, Map<Integer,List<String>> map) {
        List<String> res = new ArrayList<String>();
        // exit
        if (start == s.length()) res.add(""); // reach the end, validate string

        // check map, avoid repeated work
        if (map.containsKey(start)) return map.get(start);

        // process
        for (int e = start + 1; e <= s.length(); e++) {
            String w = s.substring(start, e);
            if (dict.contains(w)) {
                List<String> next = dfs(s, e, dict, map);
                for (String str : next) {
                    res.add(w + (str.equals("") ? "" : " ") + str);
                }
            }
        }
        map.put(start, res);

        return res;
    }
}

/*
DFS, memorization

iterate characters, if in dict, dfs check remaining:
    if substring is validate, it returns word list, append all
    else return empty list
*/