面试题 01.05.一次编辑

题目

一次编辑

思路

分类讨论：

• 当两个字符串相等时，直接返回 True
• 当两个字符串的长度相差超过2时，直接返回 False
• 当两个字符串长度相差为 1 时，则调用函数判断是否只存在一处编辑
• 当两个字符串长度相等时，遍历一遍字符串，判断每个位置的字符是否相等，若不相等的个数大于 1 时，则返回 False ，否则返回 True

题解

• 题解1

class Solution {
public:
    // a 是较大的字符串，b是较小的字符串
    bool isDelete(string a, string b){
        for(int i = 0; i < a.size(); i++){
            string str = a;
            str.erase(i, 1);  // 删除一个字符
            if(str == b) return true;
        }
        return false;
    }

    bool oneEditAway(string first, string second) {
        int firstLen = first.size();
        int secondLen = second.size();
        if(first == second) return true; 
        else if(abs(firstLen - secondLen) > 1) return false;
        else if(abs(firstLen - secondLen) == 1) { // 插入或者删除一个字符
            if(firstLen > secondLen)
                return isDelete(first, second);
            else
                return isDelete(second, first);
        }
        else {
            int num = 0;
            for(int i = 0; i < first.size(); i++){
                if(first[i] != second[i]){
                    num ++;
                }
            }
            return num == 1 || num == 0 ? true : false;
        }
    }
};

• 时间复杂度：O(n)，其中 n 是字符串的长度，最多遍历一遍字符串
• 空间复杂度：O(n)，判断是否删除时，需要找一个临时变量存储字符串

执行用时：0 ms, 在所有 C++ 提交中击败了100.00%的用户

内存消耗：6.2 MB, 在所有 C++ 提交中击败了19.66%的用户

通过测试用例：1146 / 1146