0%

[Leetcode]139. Word Break(C++)

题目描述

题目链接: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") 中时可以利用该结果节省计算时间

代码如下:

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
#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