算法基本思路:
从两个字符串中删除可以匹配的字符,然后检查剩余字符数
具体步骤:
1.遍历字符串a
2.对于a中的每个字符u,在b中查找是否存在
3.如果存在,删除a中的这个字符和b中对应位置的字符
4.如果不存在,继续检查a的下一个字符
5.处理完后,如果两个字符串剩下的字符数都≤1,则相似
为什么这个算法有正确性:
虽然看起来简单,但实际上是基于编辑距离的变形:
1.完全相同的字符串:
所有字符都能匹配删除,最终a和b都为空,长度都≤1,输出similar
2.修改一个字符:
只有一个字符不同,其他都能匹配删除,最终各剩1个字符,输出similar
3.插入/删除一个字符:
短串的所有字符都能在长串中找到,最终短串为空,长串剩1个字符,输出similar
4.不相似的情况:
会有至少2个字符无法匹配,最终某个字符串长度≥2,输出not similar
时间复杂度:
最坏情况:O(n×m),其中n、m为字符串长度
本题限制字符串长度≤50,完全在可接受范围内
代码如下:
如果不清楚find()+erase()函数的标准代码的话可以到我的主页中的U116621看