题目概述
现在有两个字符串s1和s2（长度不超过200000），Tom是一个有强迫症的人，他想要把这两个字符串变的相同。
但是每次只能删除其中一个字符串的最左端的字符，问最少需要经过多少次操作才能使这两个字符串变的相同？
输入:
输入内容为两个，第一个为字符串s1，第二个为字符串s2
输出:
输出一个数字，表示最小的操作次数
题解
解题方法
- 逆向遍历
算法知识
排序
- 时间复杂度: nlogn
- 空间复杂度: n
解题思路
审题
- String s1, s2 : 分别代表两个字符串
- 一次只能删除最左边的一个字符
题目要求
- 让两个字符串变成相同最少的操作次数
思路
- 题目要求将两个字符串删除到相同为止
- 每次只能删除最左边的字符
- 依据这两个条件, 我们得到了另一个解法：
从右侧开始遍历, 则变成了判断两个字符串中从末端开始最长的相同部分
左侧剩的就都是不同的, 全部删除掉。
步骤
定义变量
- int same : 计算两个字符串从右侧开始相同字符的个数， 初始值为0
从右侧开始遍历, 计算从右端开始相同字符的个数
- 如果两个字符串的字符相同, 则same+1
- 如果不同, 直接退出循环
- 返回两字符串字符个数之和 - 2 * same
若有收获，就点个赞吧
0 人点赞
