image.png

這個道題目一咋看，很多人肯定會覺得直接DP，因為這種是典型的DP的題目，初始條件很容易想到，推導(dǎo)式也很容易想到，寫起來清晰明了

class Solution {
public:
    bool isOneEditDistance(string s, string t) {
        vector<vector<int>> dp(s.size() + 1, vector<int>(t.size() + 1, 0));
        
        for (int i = 0; i <= s.size(); i++) {
            dp[i][0] = i;
        }
        
        for (int j = 0; j < t.size(); j++) {
            dp[0][j] = j;
        }
        
        for (int i = 1; i <= s.size(); i++) {
            for (int j = 1; j <= t.size(); j++) {
                if (s[i - 1] == t[j - 1]) {
                    dp[i][j] = dp[i - 1][j - 1];
                } else {
                    dp[i][j] = min(dp[i - 1][j], min(dp[i][j - 1], dp[i - 1][j - 1])) + 1;
                }
            }
        }
        
        return dp[s.size()][t.size()] == 1;
    }
};

上面寫的二維數(shù)組可以通過滾動數(shù)組的方式降到1維，空間復(fù)雜度O(N)，時間復(fù)雜度O(N^2)

仔細想一想，其他用DP的方式過重了，為什么呢？因為計算了所有的substring 是不是滿足one edit distance，可以通過更簡單直接的方法來優(yōu)化這個問題，如下面這個解法，關(guān)鍵點是

• 如果兩個string 長度相等，那么有且只有其中的個char值不一樣
• 如果兩個string 長度不相等，那么長度相差應(yīng)該有且等于1，且不同的地方之后應(yīng)該和原來的string相等

class Solution {
public:
    bool isOneEditDistance(string s, string t) {
        int m = s.size(), n = t.size();
        if (m > n) {
            return isOneEditDistance(t, s);
        }
        for (int i = 0; i < m; i++) {
            if (s[i] != t[i]) {
                if (m == n) {
                    return s.substr(i + 1) == t.substr(i + 1);
                }
                return s.substr(i) == t.substr(i + 1);
            }
        }
        return m + 1 == n;
    }
};