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) |
Related Problems
请尊重作者的劳动成果,转载请注明出处!花花保留对文章/视频的所有权利。
如果您喜欢这篇文章/视频,欢迎您捐赠花花。
If you like my articles / videos, donations are welcome.
花花前辈,请问下这个题目的时间复杂度和空间复杂度,谢谢:)
时间复杂度和空间复杂度都是O(2^n)
T(n) = T(0) + T(1) + … + T(n – 1) = O(2^n)
input = “abcde” dict=[“a”, “b”, “c”, “d”, “e”, “bc”, “bcd”, “bcde”, “cd”, “cde”, “de”]
“abcde”
“a bcde”
“a b cde”
“a b c de”
“a b cd e”
“a b c d e”
“a bc de”
“a bc d e”
“a bcd e”
“ab cde”
“ab c de”
“ab cd e”
“ab c d e”
“abc de”
“abc d e”
“abcd e”
你好,我有一个疑问,为什么这个空间复杂度没有考虑递归stack所占用的空间呢? 谢谢
stack所占空间应该是O(n),不在一个数量级上面,所以可以不用考虑。