【阿里云在线编程】39.复杂的字符串

写一个详细的题解练练手

周末两天连轴转竟然刷了36道题。。。到现在周一玩儿了一整天，整个双肩包应该就差不多了，键盘我大概率拿不到了。

 

 

这是一道及其简单的入门级题目，我们来梳理一下题目的结构

两个字符串变相同,只有唯一的一种操作方法就是删除左侧的字符。

给出两个字符串s1和s2（注意题目并没有说明两个字符串是等长的）。

当题目开始变换时，是这样的

（插入为gif动图使用web模式进行浏览）

 

我们很容易可以看到字符串左端是变动的而字符串右端的字符是不会发生改变的，

所以当满足字符相等的条件时，最右端的字符顺序是不会改变的，

当字符串长度不等时会优先裁剪多出来的部分，然后再判断字符串长度，保证了字符串长度的相等，然后调整字符串大小每次都砍去头一个字符，直到剩余字符串相等。

 

动态版gif

按照之前最朴素的描述我们会先裁剪字符串长度不等的部分

得到两个长度相等的字符串再进行处理

由于可活动调节范围是字符串的左侧 所以我们判断字符串不等后直接砍掉每个字符串左侧的第一个字符 判断新生成的字符串是否相等。

然后依次删除直到剩余字符串相等为止

最终得到相等字符串 返回删减次数即可。

删除最多 n次，每次删除后都需要遍历匹配剩余部分 最多判断n*n次

所以复杂度 为 n*n

这样虽然能够得到答案但是明显过于朴素，我们很容易的就能想到换一个角度进行求解。

动态版gif

 

将字符串从右侧进行对齐。

由于右侧的字符串不变，所以最终答案剩下的字符串部分是右侧连续相同的子串

所以我们很自然地想到从末尾开始进行匹配

然后依次向前推进

当不满足相等条件时可以停止，推进的字符串即为剩余的相等部分

我们需要砍掉的就是其他的前面的字符。

这样就一次遍历最短的字符串就能得到最终结果。

复杂度为1

这道题题目很简单，相信大部分人也都会做，但是题目所体现的转换思考的角度，是我们每个人在日常生活中都需要去发现的。