[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 >= ) return false;
else if (diff == ) {
for (int i = ; i < n; ++i) {
if (s[i] != t[i]) {
return s.substr(i + ) == t.substr(i);
}
}
return true;
} else {
int cnt = ;
for (int i = ; i < m; ++i) {
if (s[i] != t[i]) ++cnt;
}
return cnt == ;
}
}
};

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

解法二:

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

Github 同步地址:

https://github.com/grandyang/leetcode/issues/161

类似题目:

Edit Distance

参考资料:

https://leetcode.com/problems/one-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

LeetCode All in One 题目讲解汇总(持续更新中...)

上一篇:在Python中使用正则表达式同时匹配邮箱和电话并进行简单的分类


下一篇:【LeetCode】161. One Edit Distance