[leetcode] 161. one edit distance 一个编辑距离
given two strings s and t, determine if they are both one edit distance apart.
note:
there are 3 possiblities to satisify one edit distance apart:
- insert a character into s to get t
- delete a character from s to get t
- replace a character of s to get t
example 1:
input: s = “ab”, t = “acb” output: true
explanation: we can insert ‘c’ into s to get t.
example 2:
input: s = “cab”, t = “ad”
output: false
explanation: we cannot get t from s by only one step.
example 3:
input: s = “1203”, t = “1213”
output: true
explanation: we can replace ‘0’ with ‘1’ to get t.
这道题是之前那道 edit distance 的拓展,然而这道题并没有那道题难,这道题只让我们判断两个字符串的编辑距离是否为1,那么只需分下列三种情况来考虑就行了:
1. 两个字符串的长度之差大于1,直接返回false。
2. 两个字符串的长度之差等于1,长的那个字符串去掉一个字符,剩下的应该和短的字符串相同。
3. 两个字符串的长度之差等于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; } };
github 同步地址:
类似题目:
edit distance
参考资料:
https://leetcode.com/problems/one-edit-distance/discuss/50108/c%2b%2b-dp
https://leetcode.com/problems/one-edit-distance/discuss/50098/my-clear-java-solution-with-explanation
到此这篇关于c++实现leetcode(161.一个编辑距离)的文章就介绍到这了,更多相关c++实现一个编辑距离内容请搜索<计算机技术网(www.ctvol.com)!!>以前的文章或继续浏览下面的相关文章希望大家以后多多支持<计算机技术网(www.ctvol.com)!!>!
需要了解更多c/c++开发分享C++实现LeetCode(161.一个编辑距离),都可以关注C/C++技术分享栏目—计算机技术网(www.ctvol.com)!
本文来自网络收集,不代表计算机技术网立场,如涉及侵权请联系管理员删除。
ctvol管理联系方式QQ:251552304
本文章地址:https://www.ctvol.com/c-cdevelopment/678069.html