# 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._

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;
}
}
};

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 同步地址：

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 题目讲解汇总(持续更新中…)

 微信打赏 Venmo 打赏
（欢迎加入博主的知识星球，博主将及时答疑解惑，并分享刷题经验与总结，试运营期间前五十位可享受半价优惠～）

×

Help us with donation