给定一个非空字符串 s 和一个包含非空单词的列表 wordDict，判定 s 是否可以被空格拆分为一个或多个在字典中出现的单词。
说明：
拆分时可以重复使用字典中的单词。
你可以假设字典中没有重复的单词。示例 1：
输入: s = "leetcode", wordDict = ["leet", "code"]
输出: true
解释: 返回 true 因为 "leetcode" 可以被拆分成 "leet code"。示例 2：
输入: s = "applepenapple", wordDict = ["apple", "pen"]
输出: true
解释: 返回 true 因为 "applepenapple" 可以被拆分成 "apple pen apple"。
注意你可以重复使用字典中的单词。示例 3：
输入: s = "catsandog", wordDict = ["cats", "dog", "sand", "and", "cat"]
输出: false
- 错误的解决方案
考虑递归的方式，如果查找到匹配的单词，则判断剩余的字符串是否匹配。笔者最开始甚至实现了一个字典树。
struct CharTreeNode {
char ch;
bool end;
vector<CharTreeNode> next;
CharTreeNode() {
ch = 0;
end = false;
}
CharTreeNode(char c) {
ch = c;
end = false;
}
void SetEnd() {
end = true;
}
CharTreeNode *AppendChar(char c) {
for (int i = 0; i < next.size(); ++i) {
if (next[i].ch == c) {
return &next[i];
}
}
next.push_back(CharTreeNode(c));
return &next.back();
}
CharTreeNode *findChar(char c) {
for (int i = 0; i < next.size(); ++i) {
if (next[i].ch == c) {
return &next[i];
}
}
return nullptr;
}
};
然后首先依据给定单词构造字典树，并递归查找是否匹配。
class Solution {
public:
bool wordBreak(string s, vector<string>& wordDict) {
BuildWordTree(wordDict);
return wordSplitFind(s);
}
bool wordSplitFind(const string &s) {
if (s.empty()) {
return true;
}
CharTreeNode *p = &root;
for (int i = 0; i < s.length(); ++i) {
CharTreeNode *q = p->findChar(s[i]);
if (q == nullptr) {
return false;
}
if (q->end) {
bool ret = wordSplitFind(s.substr(i + 1));
if (ret) {
return true;
}
if (q->next.empty()) {
return false;
}
}
p = q;
}
return false;
}
void BuildWordTree(vector<string> &words) {
for (int i = 0; i < words.size(); ++i) {
string &word = words[i];
CharTreeNode *p = &root;
for (int j = 0; j < word.length(); ++j) {
p = p->AppendChar(word[j]);
}
p->SetEnd();
}
}
private:
CharTreeNode root;
};
- 动态规划算法
上述算法对于特定情况下出现执行超时的问题。换一个思路，考虑动态规划算法。以字符串当前位置判断，设为i。则flag[i] = flag[j] && (s.substr(i, j - i) == word)。
即：如果在之前j位置已经匹配，那么从j到i之间构成的字符串如果与某个单词匹配，则设置i位置也为true。
class Solution {
public:
bool wordBreak(string s, vector<string>& wordDict) {
vector<bool> flag(s.length() + 1, false);
flag[0] = true;
unordered_map<int, unordered_set<string>> mp;
int min = 0, max = 0;
for (int i = 0; i < wordDict.size(); ++i) {
int len = wordDict[i].length();
mp[len].insert(wordDict[i]);
if (i == 0) {
min = max = wordDict[i].length();
} else {
if (len > max) {
max = len;
}
if (len < min) {
min = len;
}
}
}
for (int i = 0; i < s.length(); ++i) {
flag[i + 1] = false;
int start = i + 1 - max;
int end = i + 1 - min;
for (int j = start < 0 ? 0 : start; j <= end; ++j) {
if (!flag[j]) {
continue;
}
int diff = i + 1 - j;
auto it = mp.find(diff);
if (it == mp.end()) {
continue;
}
bool find = false;
string tmp = s.substr(j, diff);
for (auto iter = it->second.begin(); iter != it->second.end(); ++iter) {
if (tmp == *iter) {
find = true;
break;
}
}
if (find) {
flag[i + 1] = true;
break;
}
}
}
return flag.back();
}
};
