[LeetCode]Word Break

Question

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.

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.

Example 1:

Input: s = “leetcode”, wordDict = [“leet”, “code”]

Output: true

Explanation: Return true because “leetcode” can be segmented as “leet code”.

Example 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.

Example 3:

Input: s = “catsandog”, wordDict = [“cats”, “dog”, “sand”, “and”, “cat”]

Output: false

Solution

解析

看到题以后,自己的想法是,暴力破解。双指针,一个指向单词的开头,一个指向结尾,将字符串切分,然后判断这个子串是否在字典里,如果再,变更左指针的位置,等于右指针位置+1,然后接着遍历,直到右指针到达字符串末尾。

这种解法的问题在于,会陷入局部解,产生错误答案(贪心,只要有就行,并不关注全局解)。比如说,字符串为s=”aaab”,wordDict=[“aa”, “aaa”, “b”]. 这种解法,最终结果是false。因为,第一次找到子串在字典中时,划分的子串是“aa”,剩下“ab”,当遍历结束时,这个剩余子串并不在字典中,导致错误结果。实际上s串可以有“aaa”+“b”组成。

感觉这个问题和上台阶差不多,我们只关注当前位置,到第i个位置能否正确切分,并不关心之前是怎么切分的。

正确的解法是用动态规划(我自己想不出来,(⊙﹏⊙)b)。

动态规划

最主要的问题是知道状态是什么,以及推出状态转移方程。知道这两个条件之后,动态规划就可以很容易写出来了(关键是想不出来,哎,菜是原罪)。

这里长为n的字符串s,对s进行切分,一维状态数组,dp[i]表明长度为i的字符串能否正确切分,最后推导出dp[n]的结果。 问题的起始状态是什么?以空串开始,也就是dp[0],初始状态为true,可以切分。所以dp数组的长度比s串的长度大1.

那么,状态转移方程怎么定义?

dp[i] = dp[j] && wordDict.find(s.substr(j, i-j))

语言表达是从0到i-1这i长的字符串,能否切分取决于dp[j]和s.substr(j, i-j),从j开始长为i-j的子串是否出现在字典中,以及dp[j]的切分结果。

dp[i] 表示长度为i的子串([0, i-1])能否正确切分。

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
class Solution {
public:
bool wordBreak(string s, vector
https://blog.csdn.net/DERRANTCM/article/details/47774547<string>& wordDict) {
unordered_set<string> words(wordDict.begin(), wordDict.end());//set保存,方便查找
vector<bool> dp(s.size()+1);
// 注意这里dp数组的长度比s串的长度大1,是因为我们要handle空串的情况
dp[0] = true;
// dp[i]表示范围[0, i)内的子串是否可以拆分;或者说长度为i的子串能否切分成功
// dp[j] 不包括下标为j的字符
for (int i=1; i<= dp.size(); i++){//i是长度,不是下标
for (int j=0; j< i; j++){//长度为i的子串划分
if (dp[j] && words.count(s.substr(j, i-j))){
dp[i] = true;
break;
}
}
}
return dp.back();
}
};

References

https://www.cnblogs.com/grandyang/p/4257740.html https://blog.csdn.net/DERRANTCM/article/details/47774547

您的支持就是我更新的最大动力!谢谢!