C++怎么判断编辑距离是否为1

这篇文章主要讲解了“c++怎么判断编辑距离是否为1”，文中的讲解内容简单清晰，易于学习与理解，下面请大家跟着小编的思路慢慢深入，一起来研究和学习“C++怎么判断编辑距离是否为1”吧！

编辑距离

这道题是之前那道 Edit Distance 的拓展，然而这道题并没有那道题难，这道题只让我们判断两个字符串的编辑距离是否为1，那么只需分下列三种情况来考虑就行了：

两个字符串的长度之差大于1，直接返回False。

两个字符串的长度之差等于1，长的那个字符串去掉一个字符，剩下的应该和短的字符串相同。

两个字符串的长度之差等于0，两个字符串对应位置的字符只能有一处不同。

分析清楚了所有的情况，代码就很好写了，参见如下：

解法一：

class Solution {public:    bool isOneEditDistance(string s, string t) {        if (s.size() < t.size()) swap(s, t);        int m = s.size(), n = t.size(), diff = m - n;        if (diff >= 2) return false;        else if (diff == 1) {            for (int i = 0; i < n; ++i) {                if (s[i] != t[i]) {                    return s.substr(i + 1) == t.substr(i);                }            }            return true;        } else {            int cnt = 0;            for (int i = 0; i < m; ++i) {                if (s[i] != t[i]) ++cnt;            }            return cnt == 1;        }    }};

我们实际上可以让代码写的更加简洁，只需要对比两个字符串对应位置上的字符，如果遇到不同的时候，这时看两个字符串的长度关系，如果相等，则比较当前位置后的字串是否相同，如果s的长度大，那么比较s的下一个位置开始的子串，和t的当前位置开始的子串是否相同，反之如果t的长度大，则比较t的下一个位置开始的子串，和s的当前位置开始的子串是否相同。如果循环结束，都没有找到不同的字符，那么此时看两个字符串的长度是否相差1，参见代码如下：

解法二：

class Solution {public:    bool isOneEditDistance(string s, string t) {        for (int i = 0; i < min(s.size(), t.size()); ++i) {            if (s[i] != t[i]) {                if (s.size() == t.size()) return s.substr(i + 1) == t.substr(i + 1);                if (s.size() < t.size()) return s.substr(i) == t.substr(i + 1);                else return s.substr(i + 1) == t.substr(i);            }        }        return abs((int)s.size() - (int)t.size()) == 1;    }};

感谢各位的阅读，以上就是“C++怎么判断编辑距离是否为1”的内容了，经过本文的学习后，相信大家对C++怎么判断编辑距离是否为1这一问题有了更深刻的体会，具体使用情况还需要大家实践验证。这里是编程网，小编将为大家推送更多相关知识点的文章，欢迎关注！