字符串相关的动态规划
标签: 机试攻略 - 高分篇
学习人数: 16.9k


高清播放
赞赏支持

字符串相关的动态题目非常多,我们选取其中最具代表性也是最常考的三个知识点


1、最长公共子串

问题描述:给出两个字符串,找到最长公共子串,并返回其长度。
输入: s = “ABCD”, t = “EABDF”
输出: 2
解释: s 和 t 的最长公共子串为 “AB”

题目解析:

 

2、最长公共子序列

问题描述:给出两个字符串,找到最长公共子序列(LCS),返回LCS的长度。
输入: s = “ABCD”, t = “EABDF”
输出: 3
解释: s 和 t 的最长公共子序列为 “ABD”

题目解析:


3、字符串相似度/编辑距离

给定两个单词 word1 和 word2,计算出将 word1 转换成 word2 所使用的最少操作数 。
你可以对一个单词进行如下三种操作:
插入一个字符
删除一个字符
替换一个字符
输入: word1 = “horse”, word2 = “ros”
输出: 3
解释:
horse -> rorse (将’h’ 替换为 ‘r’)
rorse -> rose (删除 ‘r’) rose -> ros (删除 ‘e’)

题目解析:

登录查看完整内容


课后作业

掌握字符串相关的动态规划


登录后开始许愿

暂无评论,来抢沙发