题目描述
题目链接:139. Word Break
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.
例子
例子 1
Input:
s = "leetcode", wordDict = ["leet", "code"]
Output:true
Explanation:Return true because "leetcode" can be segmented as "leet code".
例子 2
Input:
s = "applepenapple", wordDict = ["apple", "pen"]
Output:true
Explanation:Return true because "applepenapple" can be segmented as "apple pen apple".
Note that you are allowed to reuse a dictionary word.
例子 3
Input:
s = "catsandog", wordDict = ["cats", "dog", "sand", "and", "cat"]
Output:false
Note
- The same word in the dictionary may be reused multiple times in the segmentation.
- You may assume the dictionary does not contain duplicate words.
解题思路
这道题可以用记忆化递归的思路来进行求解:
- 对于题目中给出的
"leetcode"
和["leet", "code"]
,对于一整个单词,我们可以将它分解成不同的子问题来分别求解:"leetcode" --> "l" && "eetcode"
对于这两部分,我们只需要判断wordbreak("l") && dict.count("eetcode")
是否为真即可,假如为真那么对于整个"leetcode"
也可以判断为真,否则"leetcode" --> "le" && "etcode"
进行同样操作,注意由于wordbreak("l")
我们已经进行过一次计算,因此在计算wordbreak("le")
中时可以利用该结果节省计算时间
代码如下:
#include <string>
#include <unordered_map>
#include <unordered_set>
#include <vector>
class Solution {
public:
bool wordBreak(std::string s, std::vector<std::string>& wordDict) {
std::unordered_set<std::string> dict(wordDict.begin(), wordDict.end());
return wordBreak(s, dict);
}
bool wordBreak(const std::string& word,
const std::unordered_set<std::string>& dict) {
if (m_notes.count(word)) return m_notes[word];
if (word.empty() || dict.count(word)) return true;
for (int i = 1; i < word.length(); i++) {
std::string first = word.substr(0, i);
std::string second = word.substr(i);
if (wordBreak(first, dict) && dict.count(second)) {
m_notes[word] = true;
return true;
}
}
m_notes[word] = false;
return false;
}
private:
std::unordered_map<std::string, bool> m_notes;
};
- 时间复杂度: O(n^2)
- 空间复杂度: O(n^2)
GitHub 代码同步地址: 139.WordBreak.cpp
其他题目: GitHub: Leetcode-C++-Solution 博客: Leetcode-Solutions