140. Word Break II

• Time: $O(2^n)$
• Space: $O(2^n)$
  1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 class Solution { public: vector wordBreak(string s, vector& wordDict) { unordered_set wordSet{begin(wordDict), end(wordDict)}; unordered_map> memo; return wordBreak(s, wordSet, memo); } private: vector wordBreak(const string& s, const unordered_set& wordSet, unordered_map>& memo) { if (const auto it = memo.find(s); it != cend(memo)) return it->second; vector ans; // 1 <= prefix.length() < s.length() for (int i = 1; i < s.length(); ++i) { const string& prefix = s.substr(0, i); const string& suffix = s.substr(i); if (wordSet.count(prefix)) for (const string& word : wordBreak(suffix, wordSet, memo)) ans.push_back(prefix + " " + word); } // Contains whole string, so don't add any space if (wordSet.count(s)) ans.push_back(s); return memo[s] = ans; } }; 
  1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 class Solution { public List wordBreak(String s, List wordDict) { Set wordSet = new HashSet<>(wordDict); Map> memo = new HashMap<>(); return wordBreak(s, wordSet, memo); } private List wordBreak(final String s, Set wordSet, Map> memo) { if (memo.containsKey(s)) return memo.get(s); List ans = new ArrayList<>(); // 1 <= prefix.length() < s.length() for (int i = 1; i < s.length(); ++i) { final String prefix = s.substring(0, i); final String suffix = s.substring(i); if (wordSet.contains(prefix)) for (final String word : wordBreak(suffix, wordSet, memo)) ans.add(prefix + " " + word); } // Contains whole string, so don't add any space if (wordSet.contains(s)) ans.add(s); memo.put(s, ans); return ans; } } 
  1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 class Solution: def wordBreak(self, s: str, wordDict: List[str]) -> List[str]: wordSet = set(wordDict) @functools.lru_cache(None) def wordBreak(s: str) -> List[str]: ans = [] # 1 <= len(prefix) < len(s) for i in range(1, len(s)): prefix = s[0:i] suffix = s[i:] if prefix in wordSet: for word in wordBreak(suffix): ans.append(prefix + ' ' + word) # Contains whole string, so don't add any space if s in wordSet: ans.append(s) return ans return wordBreak(s)