Problem
Given a non-empty string s and 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
Time complexity: O(2^n)
Space complexity: O(2^n)
C++
|
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 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 |
// Author: Huahua class Solution { public: vector<string> wordBreak(string s, vector<string>& wordDict) { unordered_set<string> dict(wordDict.cbegin(), wordDict.cend()); return wordBreak(s, dict); } private: // >> append({"cats and", "cat sand"}, "dog"); // {"cats and dog", "cat sand dog"} vector<string> append(const vector<string>& prefixes, const string& word) { vector<string> results; for(const auto& prefix : prefixes) results.push_back(prefix + " " + word); return results; } const vector<string>& wordBreak(string s, unordered_set<string>& dict) { // Already in memory, return directly if(mem_.count(s)) return mem_[s]; // Answer for s vector<string> ans; // s in dict, add it to the answer array if(dict.count(s)) ans.push_back(s); for(int j=1;j<s.length();++j) { // Check whether right part is a word const string& right = s.substr(j); if (!dict.count(right)) continue; // Get the ans for left part const string& left = s.substr(0, j); const vector<string> left_ans = append(wordBreak(left, dict), right); // Notice, can not use mem_ here, // since we haven't got the ans for s yet. ans.insert(ans.end(), left_ans.begin(), left_ans.end()); } // memorize and return mem_[s].swap(ans); return mem_[s]; } private: unordered_map<string, vector<string>> mem_; }; |
Python3
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 |
""" Author: Huahua Running time: 56 ms """ class Solution: def wordBreak(self, s, wordDict): words = set(wordDict) mem = {} def wordBreak(s): if s in mem: return mem[s] ans = [] if s in words: ans.append(s) for i in range(1, len(s)): right = s[i:] if right not in words: continue ans += [w + " " + right for w in wordBreak(s[0:i])] mem[s] = ans return mem[s] return wordBreak(s) |