首页 > 代码库 > leetcode[161] One Edit Distance

leetcode[161] One Edit Distance

判断两个字符串的编辑距离是不是1.

关于编辑距离可以参见之前有一题leetcode[72] Edit Distance

思路:

如果字符串相差2个以及以上长度,那么肯定不止1,直接false

如果字符串长度相等,那么判断对应位置不同的字符数是不是1即可。

如果字符串长度相差1,那么肯定是要在长的那个串删掉一个,所以两个字符串一起加加,一旦遇到一个不同,那么剩下的子串就要是一样,否则就是不止一个不同,false。

    bool isOneDifL(string s, string t)    {        for (int i = 0; i < s.size(); i++)        {            if (s[i] == t[i])                continue;            return s.substr(i) == t.substr(i+1);        }        return true; // 说明前面的都相等只有最后一个不匹配    }    bool isSameLen(string s, string t)    {        int cnt = 0;        for (int i = 0; i < s.size(); i++)        {            if (s[i] != t[i])                cnt++;        }        return cnt == 1;    }    bool isOneEditDistance(string s, string t)    {        if (abs(s.size() - t.size()) > 1) return false;        if (s.size() == t.size()) return isSameLen(s, t);        else if (s.size() < t.size()) return isOneDifL(s, t);        else return isOneDifL(t, s);    }

还可以参见一个函数搞定的,巧妙的合在一起

    bool isOneEditDistance2(string s, string t){        if (s.length() > t.length()) {            swap(s,t);        }        if (t.length() - s.length() > 1) {            return false;        }        bool have = false;        for (int i = 0, j = 0; i < s.length(); ++i,++j){            if (s[i] != t[j]) {                if (have) {                    return false;                }                have = true;                if (s.length() < t.length()) {                    --i;                }            }        }        return (have) || (s.length() < t.length());    }

 

leetcode[161] One Edit Distance