c/c++语言开发共享C++实现LeetCode(161.一个编辑距离)

[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:

1. insert a character into s to get t
2. delete a character from s to get t
3. 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)!