Problem
Given a non-empty string s and a dictionary wordDict containing a list of non-empty words, determine if s can be segmented into a space-separated sequence of one or more dictionary words. You may assume the dictionary does not contain duplicate words.
For example, given
s = "leetcode",
dict = ["leet", "code"].
Return true because "leetcode" can be segmented as "leet code".
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.
Idea:
DP
Time complexity O(n^2)
Space complexity O(n^2)
Solutions:
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 |
// Author: Huahua class Solution { public: bool wordBreak(string s, vector<string>& wordDict) { // Create a hashset of words for fast query. unordered_set<string> dict(wordDict.cbegin(), wordDict.cend()); // Query the answer of the original string. return wordBreak(s, dict); } bool wordBreak(const string& s, const unordered_set<string>& dict) { // In memory, directly return. if(mem_.count(s)) return mem_[s]; // Whole string is a word, memorize and return. if(dict.count(s)) return mem_[s]=true; // Try every break point. for(int j=1;j<s.length();j++) { const string left = s.substr(0,j); const string right = s.substr(j); // Find the solution for s. if(dict.count(right) && wordBreak(left, dict)) return mem_[s]=true; } // No solution for s, memorize and return. return mem_[s]=false; } private: unordered_map<string, bool> mem_; }; |
C++ V2 without using dict. Updated: 1/9/2018
|
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 |
// Author: Huahua // Running time: 9 ms class Solution { public: bool wordBreak(string s, vector<string>& wordDict) { // Mark evert word as breakable. for (const string& word : wordDict) mem_.emplace(word, true); // Query the answer of the original string. return wordBreak(s); } bool wordBreak(const string& s) { // In memory, directly return. if (mem_.count(s)) return mem_[s]; // Try every break point. for (int j = 1; j < s.length(); j++) { auto it = mem_.find(s.substr(j)); // Find the solution for s. if (it != mem_.end() && it->second && wordBreak(s.substr(0, j))) return mem_[s] = true; } // No solution for s, memorize and return. return mem_[s] = false; } private: unordered_map<string, bool> mem_; }; |
Java
|
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 |
// Author: Huahua // Runtime: 13 ms class Solution { public boolean wordBreak(String s, List<String> wordDict) { Set<String> dict = new HashSet<String>(wordDict); Map<String, Boolean> mem = new HashMap<String, Boolean>(); return wordBreak(s, mem, dict); } private boolean wordBreak(String s, Map<String, Boolean> mem, Set<String> dict) { if (mem.containsKey(s)) return mem.get(s); if (dict.contains(s)) { mem.put(s, true); return true; } for (int i = 1; i < s.length(); ++i) { if (dict.contains(s.substring(i)) && wordBreak(s.substring(0, i), mem, dict)) { mem.put(s, true); return true; } } mem.put(s, false); return false; } } |
Python
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 |
""" Author: Huahua Runtime: 42 ms """ class Solution(object): def wordBreak(self, s, wordDict): def canBreak(s, m, wordDict): if s in m: return m[s] if s in wordDict: m[s] = True return True for i in range(1, len(s)): r = s[i:] if r in wordDict and canBreak(s[0:i], m, wordDict): m[s] = True return True m[s] = False return False return canBreak(s, {}, set(wordDict)) |
请尊重作者的劳动成果，转载请注明出处！花花保留对文章／视频的所有权利。
如果您喜欢这篇文章／视频，欢迎您捐赠花花。
If you like my articles / videos, donations are welcome.
huahualeetcode
More clear code below FYI.
class Solution {
public:
bool wordBreak(string s, vector& wordDict) {
for (auto word : wordDict)
m.emplace(word, true);
return wBreak(s, wordDict);
}
bool wBreak(string &s, vector& wordDict) {
if (m.count(s)) return m[s];
for (auto word : wordDict) {
string left = s.substr(0, word.size());
if (!m.count(left) || m[left] == false) continue;
string right = s.substr(word.size());
if (wBreak(right, wordDict)) return m[s]=true;
}
return m[s]=false;
}
private:
unordered_map m;
};