【LeetCode】不同的子序列 Java 题解
题目
给定一个字符串 s 和一个字符串 t ,计算在 s 的子序列中 t 出现的个数。
字符串的一个 子序列 是指,通过删除一些(也可以不删除)字符且不干扰剩余字符相对位置所组成的新字符串。(例如,"ACE" 是 "ABCDE" 的一个子序列,而 "AEC" 不是)
题目数据保证答案符合 32 位带符号整数范围。
代码
复制代码
总结
今天的 LeetCode 题目是 hard 题目,题目的类型是 hard。这个题目是动态规划的应用,需要用心去找转移方程。
先根据题目构建图,得到初始值,然后将测试 case 带入,分析相等和不相等的情况,找出动态转移方程。
题目还是需要反复思考,过变数,加深理解和思考。
坚持每日一题,加油!
版权声明: 本文为 InfoQ 作者【HQ数字卡】的原创文章。
原文链接:【http://xie.infoq.cn/article/baa4e5096f935c06eb9562ff1】。文章转载请联系作者。
评论