[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，長的那個字符串去掉一個字符，剩下的應(yīng)該和短的字符串相同。

3. 兩個字符串的長度之差等于0，兩個字符串對應(yīng)位置的字符只能有一處不同。

分析清楚了所有的情況，代碼就很好寫了，參見如下：

解法一：

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

我們實際上可以讓代碼寫的更加簡潔，只需要對比兩個字符串對應(yīng)位置上的字符，如果遇到不同的時候，這時看兩個字符串的長度關(guān)系，如果相等，則比較當前位置后的字串是否相同，如果s的長度大，那么比較s的下一個位置開始的子串，和t的當前位置開始的子串是否相同，反之如果t的長度大，則比較t的下一個位置開始的子串，和s的當前位置開始的子串是否相同。如果循環(huán)結(jié)束，都沒有找到不同的字符，那么此時看兩個字符串的長度是否相差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

到此這篇關(guān)于C++實現(xiàn)LeetCode(161.一個編輯距離)的文章就介紹到這了,更多相關(guān)C++實現(xiàn)一個編輯距離內(nèi)容請搜索腳本之家以前的文章或繼續(xù)瀏覽下面的相關(guān)文章希望大家以后多多支持腳本之家！

最新評論