題目

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

解題之法

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

分析

這道題是之前那道Edit Distance的拓展，然而這道題并沒有那道題難，這道題只讓我們判斷兩個(gè)字符串的編輯距離是否為1，那么我們只需分下列三種情況來考慮就行了：

1. 兩個(gè)字符串的長度之差大于1，那么直接返回False

2. 兩個(gè)字符串的長度之差等于1，那么長的那個(gè)字符串去掉一個(gè)字符，剩下的應(yīng)該和短的字符串相同

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

分析清楚了所有的情況，代碼就很好寫了。