题目分析
之前我一直都在刷矩阵型,背包型的dp题目,今天我们来一道存在型的dp,这道题我觉得是比较有意思一点吧。(其实是相对简单一点,容易分析,困难题写不动,菜QAQ)
我相信很多小伙伴刷题都是为了应付面试,而应付面试,简单到中等的题目其实就够了,大部分公司都不会出很难的。再说了我只是个切图仔,困难题一般也hold不住啊,流下了没有技术的泪水。
题目分析
拿到题目我同样是先暴力解决,暴力解决我就不分析不写代码了,感兴趣的小伙伴们可以看我之前的文章,如果不考虑性能,回溯法是真香。
仔细观察题目,'leetcode' 返回 true 是因为可以被拆分为 ['leet','code'] 这两个单词,那最后一步是啥?就是 'code' 这个单词呀,再加上 'leet', 不就是答案了吗?这不是废话吗?这真不是废话,这是动态规划的题目套路,如果小伙伴们还达不到这种功力,你只需认真花费一段时间研究我之前写过的动态规划的文章,好好学习,我相信你动态规划绝对比我厉害很多;因为我真的很笨。
关于我为什么会这样思考题目,是因为我做了一段时间的dp题目了。有一定的经验,这种经验一旦你愿意花费点时间来积累,简单到中等的题目绝对是没有问题的,就看你能不能坚持下来了。
这种简单到中等的题目,我敢说90%都是直接根据示例答案去思考,思考最后一步,最优策略是什么,你想清楚了立马能写出答案。
- 定义状态
- 这里我再强调一遍,最有一步,最优策略是什么?最后一步就是code,上一步就是leet呀,那我们完全可以往问题的规模小的方向想,对应原字符串s,如果我们s='leet',答案肯定很简单,但是再加一个'code',我们该怎么办呢?假设a='leet', b='code',那问题不就变成匹配这两个ab了,当a存在,且b也存在;答案不就出来了吗?
- 所以我们可以这样来定义状态,dp[j]表示,在原串上,由i到j的子串在不在字典中。
- 状态转移方程:dp[j] = map.has(s.substring(i, j)) and dp[i]
- map.has(s.substring(i, j)) i到j在不在字典中,dp[i] 表示前面一段也在字典中
- 边界和初始条件
- 初始值,也就是base case,初始值有些特殊,因为当我们判断 a 和 b 两段都在的情况下,此时是完全匹配上了,但是我们需要一个值来递推,怎么办呢?那就让子串为空的时候为真,方便我们递推,所以dp[0] = true
- 边界,需要用到一个空串,所有就是length + 1
代码
var wordBreak = function(s, wordDict) {
let n = s.length;
let dict = new Set(wordDict);
let dp = Array(n+1).fill(false);
dp[0] = true
for(let j = 1; j < n + 1; j++){
for(let i = 0; i < j; i++){
if(dict.has(s.substring(i, j)) && dp[i]){
dp[j] = true;
break;
}
}
}
return dp[n]
};
总结
面试题很多题目都是简单或者中等的dp题目,而这类的题目并不难,你只需要判断一下能不能用dp来做,同时直接根据示例答案思考,往问题规模小的方向来思考,由局部最优递推全局最优来定义状态,思考转移方程;往往这类题目的转移方程真的不难,只需要你入门就能很轻松的解决了。