LeetCode 161 One Edit Distance

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

Diffculty Medium

Similar Problems [[LeetCode 72] Edit Distance][] h

Analysis

这道题比 Edit Distance 那道题简单，因为这道题只让我们判断两个字符串的编辑距离是否为 1，那么只需分下列三种情况来考虑就行了：

• (1). 两个字符串的长度之差大于 1，那么直接返回 False
• (2). 两个字符串的长度之差等于 1，那么先找到两个字符串中不同的字符所在的位置，长的那个不同的字符后的字符串应该和短的后半部分字符串相同
• (3). 两个字符串的长度之差等于 0，那么两个字符串对应位置的字符只能有一处不同。

思路二 我们实际上可以让代码写的更加简洁，只需要对比两个字符串对应位置上的字符，如果遇到不同的时候，这时我们看两个字符串的长度关系，如果相等，那么我们比较当前位置后的字串是否相同，如果s的长度大，那么我们比较s的下一个位置开始的子串，和t的当前位置开始的子串是否相同，反之如果t的长度大，那么我们比较t的下一个位置开始的子串，和s的当前位置开始的子串是否相同。如果循环结束，都没有找到不同的字符，那么此时我们看两个字符串的长度是否相差1。

Solutions

解法一

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

解法二

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);
                else if (s.size() < t.size()) return s.substr(i) == t.substr(i + 1);
                else return s.substr(i + 1) == t.substr(i);
            }
        }
        return abs(s.size() - t.size()) == 1;
    }
};

Reference

[[LeetCode 72] Edit Distance]:https://leetcode.com/problems/edit-distance