161. One Edit Distance
Given two strings s and t, return true if they are both one edit distance apart, otherwise return false.
A string s is said to be one distance apart from a string t if you can:
- Insert exactly one character into s to get t.
- Delete exactly one character from s to get t.
- Replace exactly one character of s with a different character to get t.
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
| class Solution {
private:
bool isInsert(string &s, string &t) {
bool ret = false;
if(t.length() == 0)
return true;
for(int i = 0, j = 0; i < s.length() && j < t.length(); i++, j++) {
if(s[i] == t[j])
continue;
if(ret)
return false;
ret = true;
--j;
}
return true;
}
bool isReplace(string &s, string &t) {
bool ret = false;
for(int i = 0; i < s.length(); i++) {
if(s[i] == t[i])
continue;
if(ret)
return false;
ret = true;
}
return ret;
}
public:
bool isOneEditDistance(string s, string t) {
return abs((int)s.length() - (int)t.length()) == 1 ? isInsert(s.length() > t.length() ? s : t, s.length() > t.length() ? t : s) : s.length() == t.length() ? isReplace(s, t) : false;
}
};
|
