题解 | #编辑距离为一# O(n)时间复杂度，双向遍历

#include <cmath>
class Solution {
public:
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     * 
     * @param s string字符串 
     * @param t string字符串 
     * @return bool布尔型
     */
    bool editdistance(string s, string t) {
        // write code here
        int n=s.length();
        int m=t.length();
        if(abs(n-m)>1)
        {
            return false;
        }
        int c1=-1,c2=-1;// 记录错误位置
        int i=0,j=0;

        // 从左往右找错误位置
        while(i<n&&j<m&&s[i]==t[j])
        {
            i++;j++;
        }
        c1=j;
        i=n-1;j=m-1;

        //从右边往左找错误位置
        while(s[i]==t[j]&&i>=0&&j>=0)
        {
            i--;j--;
        }
        c2=j;

        // 如果两个方向找出来的错误位置差距超过2 说明有1个以上的错误 或者没有错误
        if(abs(c1-c2)<=2)
        {
            return true;
        }

        return false;
    }
};