题目描述
给定一个非空字符串 s 和一个包含非空单词列表的字典 wordDict，判定 s 是否可以被空格拆分为一个或多个在字典中出现的单词。说明：
- 拆分时可以重复使用字典中的单词。
- 你可以假设字典中没有重复的单词。
题解
字符串的大多数问题都是动态规划。
1
2
3
4
| dp[i] = ( dp[i-1] && contains(subStr(i-1,i)) )
|| ( dp[i-2] && contains(subStr(i-2,i)) )
|| ( dp[i-3] && contains(subStr(i-3,i)) )
|| ...
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
| bool wordBreak(string s, vector<string>& wordDict) {
int slen = s.length();
bool* dp = new bool[slen+1];
dp[0] = true;
for (int i = 1; i <= slen; i++)
dp[i] = false;
unordered_set<string> ss;
ss.insert(std::begin(wordDict), std::end(wordDict));
for (int i = 1; i <= slen; i++)
{
for (int j = 0; j < i; j++)
{
if (dp[j] && ss.count(s.substr(j, i - j)))
{
dp[i] = true;
break;
}
}
}
return dp[slen];
}
|