阅读 514

动态规划之单词拆分

题目分析

之前我一直都在刷矩阵型,背包型的dp题目,今天我们来一道存在型的dp,这道题我觉得是比较有意思一点吧。(其实是相对简单一点,容易分析,困难题写不动,菜QAQ)

我相信很多小伙伴刷题都是为了应付面试,而应付面试,简单到中等的题目其实就够了,大部分公司都不会出很难的。再说了我只是个切图仔,困难题一般也hold不住啊,流下了没有技术的泪水。

题目分析

拿到题目我同样是先暴力解决,暴力解决我就不分析不写代码了,感兴趣的小伙伴们可以看我之前的文章,如果不考虑性能,回溯法是真香。

仔细观察题目,'leetcode' 返回 true 是因为可以被拆分为 ['leet','code'] 这两个单词,那最后一步是啥?就是 'code' 这个单词呀,再加上 'leet', 不就是答案了吗?这不是废话吗?这真不是废话,这是动态规划的题目套路,如果小伙伴们还达不到这种功力,你只需认真花费一段时间研究我之前写过的动态规划的文章,好好学习,我相信你动态规划绝对比我厉害很多;因为我真的很笨。

关于我为什么会这样思考题目,是因为我做了一段时间的dp题目了。有一定的经验,这种经验一旦你愿意花费点时间来积累,简单到中等的题目绝对是没有问题的,就看你能不能坚持下来了。

这种简单到中等的题目,我敢说90%都是直接根据示例答案去思考,思考最后一步,最优策略是什么,你想清楚了立马能写出答案。

  1. 定义状态
  • 这里我再强调一遍,最有一步,最优策略是什么?最后一步就是code,上一步就是leet呀,那我们完全可以往问题的规模小的方向想,对应原字符串s,如果我们s='leet',答案肯定很简单,但是再加一个'code',我们该怎么办呢?假设a='leet', b='code',那问题不就变成匹配这两个ab了,当a存在,且b也存在;答案不就出来了吗?
  • 所以我们可以这样来定义状态,dp[j]表示,在原串上,由i到j的子串在不在字典中。
  1. 状态转移方程:dp[j] = map.has(s.substring(i, j)) and dp[i]
  • map.has(s.substring(i, j)) i到j在不在字典中,dp[i] 表示前面一段也在字典中
  1. 边界和初始条件
  • 初始值,也就是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来做,同时直接根据示例答案思考,往问题规模小的方向来思考,由局部最优递推全局最优来定义状态,思考转移方程;往往这类题目的转移方程真的不难,只需要你入门就能很轻松的解决了。

关注下面的标签,发现更多相似文章
评论