本道题个人解法—通过字符串的删除判断

算法基本思路：
从两个字符串中删除可以匹配的字符，然后检查剩余字符数
具体步骤：
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，完全在可接受范围内

代码如下：

#include<bits/stdc++.h>
using namespace std;
int main()
{
    int n;
    cin >> n;
    while(n--)
    {
        string a,b;
        cin >> a >> b;
        for(int i = 0; i < a.length();)  // 注意：没有i++，因为删除字符后i会自动指向下一个字符
        {
            char u = a[i];               // 当前要匹配的字符
            size_t pos = b.find(u);      // 在b中寻找相同的字符
            if(pos != std::string::npos) // 如果找到了
            {
                a.erase(i,1);           // 从a中删除当前字符
                b.erase(pos,1);         // 从b中删除找到的字符
                // 这里i不自增！因为a[i]现在是原来的下一个字符
            }
            else
            {
                i++;                     // 没找到，检查a的下一个字符
            }
        }              
        int k = a.size();               // a中剩余的字符数
        int y = b.size();               // b中剩余的字符数  
        // 关键判断：如果两串都剩0-1个字符，说明编辑距离≤1
        if(k <= 1 && y <= 1)
        {
            cout << "similar" << endl;    // 相似
        }
        else
        {
            cout << "not similar" << endl; // 不相似
        }
    }
    return 0;
}

如果不清楚find()+erase()函数的标准代码的话可以到我的主页中的U116621看