# [LeetCode] One Edit Distance

+关注继续查看

Problem Description:

Given two strings S and T, determine if they are both one edit distance apart.

To solve this problem, you first need to know what is edit distance. You may refer to this wikipedia article for more information.

For this problem, it implicitly assumes to use the classic Levenshtein distance, which involvesinsertion, deletion and substitution operations and all of them are of the same cost. Thus, if Sis one edit distance apart from TT is automatically one edit distance apart from S.

Now let's think about the possible cases for two strings to be one edit distance apart. Well, that means, we can transform S to T by using exactly one edit operation. There are three possible cases:

1. We insert a character into S to get T.
2. We delete a character from S to get T.
3. We substitute a character of S to get T.

For cases 1 and 2, S and T will be one apart in their lengths. For cases 3, they are of the same length.

It is relatively easy to handle case 3. We simply traverse both of them and compare the characters at the corresponding position. If we find exactly one mismatch during the traverse, they are one edit distance apart.

Now let's move on to cases 1 and 2. In fact, they can be merged into one case, that is, to delete a character from the long string to get the short one, or equivalently, to insert a character into the short string to get the long one.

We will handle cases 1 and 2 using the short string as the reference. We traverse the two strings, once we find a mismatch. We know this position is where the deletion in the long string happens. For example, suppose S = "kitten" and T = "kiten", we meet the first mismatch in the 4-th position, which corresponds to the deleted character below, shown in between *. We then continue to compare the remaining string of T (en) with the remaining string of S (en) and find them to be the same. So they are one edit distance apart.

S: k i t t e n

T: k i t *t* e n

In fact, cases 1, 2 and 3 can be further handled using the same piece of code. For strings of the same length, once we find a mismatch, we just substitute one to be another and check whether they are now the same. For strings of one apart in lengths, we insert the deleted character of the long string into the short one and compare whether they are the same.

The code is as follows. If you find the first half of the return statement (!mismatch && (n - m == 1)) hard to understand, run the code on cases that the mismatch only occurs at the last character of the long string, like S = "ab" and T = "abc".

 1 class Solution {
2 public:
3     bool isOneEditDistance(string s, string t) {
4         int m = s.length(), n = t.length();
5         if (m > n) return isOneEditDistance(t, s);
6         if (n - m > 1) return false;
7         bool mismatch = false;
8         for (int i = 0, j = 0; i < m; i++, j++) {
9             if (s[i] != t[j]) {
10                 if (m == n) s[i] = t[j];
11                 else s.insert(i, 1, t[j]);
12                 mismatch = true;
13                 break;
14             }
15         }
16         return (!mismatch && (n - m == 1)) || (mismatch && s == t);
17     }
18 };  LeetCode 72. Edit Distance

14 0 LeetCode之Hamming Distance
LeetCode之Hamming Distance
58 0 LeetCode 461 Hamming Distance（汉明距离）
1508 0 [LeetCode] One Edit Distance 一个编辑距离
1267 0 [LeetCode] Shortest Word Distance 最短单词距离
1070 0 [LeetCode] Hamming Distance 汉明距离
1172 0 [LeetCode] Total Hamming Distance 全部汉明距离
1099 0 [LeetCode] Edit Distance 编辑距离
1042 0 [LeetCode] Shortest Word Distance
Problem Description: Given a list of words and two words word1 and word2, return the shortest distance between these two words in the list.
799 0 [LeetCode] Edit Distance
This is a classic problem of Dynamic Programming. We define the state dp[i][j] to be the minimum number of operations to convert word1[0.
703 0
jianchao_li