算法笔试模拟题精解之“复杂的字符串”
算法笔试模拟题精解之“复杂的字符串”
贡献者 | 韩旭
简介：这是一道极其简单的入门级题目，我们来梳理一下题目的结构：两个字符
串变相同 , 只有唯一的一种操作方法就是删除左侧的字符。
题目描述
等级：容易
知识点：字符串
查看题目：复杂的字符串
现在有两个字符串 s1 和 s2（长度不超过 200000），Tom 是一个有强迫症的人，
他想要把这两个字符串变的相同，但是每次只能删除其中一个字符串的最左端的字
符，问最少需要经过多少次操作才能使这两个字符串变的相同。
输入内容为两个，第一个为字符串 s1，第二个为字符串 s2。
输出一个数字，表示最小的操作次数。
示例 1
输入：
"dadc"
"dddc"
输出：
题解描述
这是一道极其简单的入门级题目，我们来梳理一下题目的结构：两个字符串变相
同 , 只有唯一的一种操作方法就是删除左侧的字符。
给出两个字符串 s1 和 s2（注意题目并没有说明两个字符串是等长的）。
当题目开始变换时，是这样的：
（插入为 gif 动图使用 web 模式进行浏览）
我们很容易可以看到字符串左端是变动的而字符串右端的字符是不会发生改变的，
所以当满足字符相等的条件时，最右端的字符顺序是不会改变的，
当字符串长度不等时会优先裁剪多出来的部分，然后再判断字符串长度，保证
了字符串长度的相等，然后调整字符串大小每次都砍去头一个字符，直到剩余字符
串相等。
动态版 gif
按照之前最朴素的描述我们会先裁剪字符串长度不等的部分，
得到两个长度相等的字符串再进行处理。
由于可活动调节范围是字符串的左侧所以我们判断字符串不等后直接砍掉每个
字符串左侧的第一个字符判断新生成的字符串是否相等。
然后依次删除直到剩余字符串相等为止。
最终得到相等字符串返回删减次数即可。
删除最多 n 次，每次删除后都需要遍历匹配剩余部分最多判断 n*n 次
所以复杂度为 n*n
这样虽然能够得到答案但是明显过于朴素，我们很容易的就能想到换一个角度进
行求解。
动态版 gif
将字符串从右侧进行对齐。
由于右侧的字符串不变，所以最终答案剩下的字符串部分是右侧连续相同的子
串 , 所以我们很自然地想到从末尾开始进行匹配。
然后依次向前推进当不满足相等条件时可以停止，推进的字符串即为剩余的相等
部分。
我们需要砍掉的就是其他的前面的字符。
这样就一次遍历最短的字符串就能得到最终结果。
复杂度为 1
这道题题目很简单，相信大部分人也都会做，但是题目所体现的转换思考的角
度，是我们每个人在日常生活中都需要去发现的。
是不是有思路了呢，点击链接立刻答题：复杂的字符串
全站分卷索引 · 74 卷
- 1一、算法思想
- 2算法笔试模拟题精解之“打怪兽”
- 31.2 贪心
- 4算法笔试模拟题精解之“最强的团队”
- 5算法笔试模拟题精解之“Tom 爱吃巧克力”
- 6算法笔试模拟题精解之“吃奶酪”
- 7算法笔试模拟题精解之“一的个数”
- 8算法笔试模拟题精解之“Bob 的花束”
- 9算法笔试模拟题精解之“钱庄”
- 10算法笔试模拟题精解之“移动射击”
- 11算法笔试模拟题精解之“相似数组”
- 12算法笔试模拟题精解之“过吊桥”
- 13算法笔试模拟题精解之“完美排列”
- 14算法笔试模拟题精解之“采摘圣诞果”
- 15算法比赛模拟题精解之“Tairitsu and Dynamic Objects”
- 16算法笔试模拟题精解之“Codancer 的炸弹引爆”
- 17算法笔试模拟题精解之“学习小组”
- 18算法笔试模拟题精解之“恢复字符串”
- 191.3 DP/ 动态规划
- 20算法笔试模拟题精解之“寻找等比数列”
- 21算法笔试模拟题精解之“字符配对”
- 22算法笔试模拟题精解之“数组染色”
- 23算法笔试模拟题精解之“连绵的群山”
- 24算法笔试模拟题精解之“难住Tom 的问题”
- 25算法笔试模拟题精解之“变化的字符”
- 26算法笔试模拟题精解之“跳房子”
- 27算法笔试模拟题精解之“寒假活动”
- 28算法笔试模拟题精解之“最短路”
- 29算法笔试模拟题精解之“codancer 上楼”
- 30算法笔试模拟题精解之“木棒拼接”
- 31算法笔试模拟题精解之“Codancer 的数组封印”
- 32算法笔试模拟题精解之“Jerry 的异或运算”
- 33算法笔试模拟题精解之“小明的数学作业”
- 34算法笔试模拟题精解之“奇偶数列”
- 351.4 剪枝
- 361.5 尺取法
- 37算法笔试模拟题精解之“调整数组”
- 38算法笔试模拟题精解之“最优分组”
- 39算法笔试模拟题精解之“破译密码”
- 40二、数据结构
- 412.2 搜索
- 42算法笔试模拟题精解之“能量半径”
- 43算法笔试模拟题精解之“苹果收获程序”
- 44算法笔试模拟题精解之“恐怖的辐射”
- 45算法笔试模拟题精解之“树的拆分”
- 46算法笔试模拟题精解之“Password”
- 47算法笔试模拟题精解之“神奇数字在哪里”
- 48算法笔试模拟题精解之“神奇的棋子”
- 492.3 树
- 50算法笔试模拟题精解之“Codancer 的旅行”
- 51算法笔试模拟题精解之“Codancer 的求和”
- 52算法笔试模拟题精解之“找出二叉搜索树的第2 大的数”
- 532.4 线型
- 54算法笔试模拟题精解之“最活跃的数”
- 55算法笔试模拟题精解之“非递减序列”
- 56算法笔试模拟题精解之“Tom 跳方格”
- 57算法笔试模拟题精解之“复杂的字符串”
- 58算法笔试模拟题精解之“神秘消失”
- 59三、计算
- 60算法笔试模拟题精解之“简单题？
- 61算法笔试模拟题精解之“朋友一生一起走”
- 62算法笔试模拟题精解之“正三角塔”
- 63算法笔试模拟题精解之“组队难题”
- 64算法笔试模拟题精解之“2n 合体”
- 65算法笔试模拟题精解之“平行线”
- 66算法笔试模拟题精解之“叠叠高”
- 67算法笔试模拟题精解之“公平”
- 68算法笔试模拟题精解之“Tom 的手工课”
- 69算法笔试模拟题精解之“填数问题”
- 70算法笔试模拟题精解之“Jerry 的考验”
- 71算法笔试模拟题精解之“超车”
- 72算法笔试模拟题精解之“坏掉的时钟”
- 73算法笔试模拟题精解之“期末考试”
- 74算法笔试模拟题精解之“滑雪比赛”