C++实现LeetCode(161.一个编辑距离)

题目解析

编辑距离（Edit Distance）是指将一个字符串转换成另一个字符串所需的最少单字符编辑操作次数。本题要求判断两个字符串的编辑距离是否恰好为 1。

满足“一次编辑距离”的情况有三种：

1. 插入：在字符串 s 中插入一个字符得到 t。
2. 删除：从字符串 s 中删除一个字符得到 t（等同于在 t 中插入一个字符得到 s）。
3. 替换：将字符串 s 中的一个字符替换为另一个字符得到 t。

解题思路

我们可以根据两个字符串长度的关系来简化问题：

1. 长度差大于 1：无论怎么编辑，至少需要两次操作才能弥补长度差距，直接返回 false。
2. 长度差等于 1：长字符串去掉某个位置的一个字符后，剩余部分必须与短字符串完全相同。这意味着在遍历时，如果找到一个不同字符，则必须确保剩余部分匹配。
3. 长度相等：两个字符串只能有一个位置的字符不同，其余位置必须完全一致。

C++ 代码实现

解法一：分类讨论

首先保证 s 是较长或等长的字符串。然后分别处理长度差为 1 和长度相等的情况。

class Solution {
public:
    bool isOneEditDistance(string s, string t) {
        // 确保 s 是较长的字符串，便于统一处理
        if (s.size() < t.size()) swap(s, t);
        
        int m = s.size(), n = t.size();
        int diff = m - n;
        
        // 长度差超过1，不可能是一次编辑
        if (diff >= 2) return false;
        
        // 长度为差1：尝试删除 s 中的一个字符使其等于 t
        else if (diff == 1) {
            for (int i = 0; i < n; ++i) {
                // 找到第一个不同的位置
                if (s[i] != t[i]) {
                    // 检查 s 删除该字符后剩余部分是否与 t 剩余部分相同
                    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;
        }
    }
};

解法二：简洁遍历

这种方法更加通用且代码更简洁。我们只遍历较短字符串的长度，一旦发现不同字符，立即根据长度关系判断后续子串是否匹配。如果遍历结束都没有发现不同，则仅当长度差为 1 时才成立。

class Solution {
public:
    bool isOneEditDistance(string s, string t) {
        int lenS = s.size(), lenT = t.size();
        
        // 遍历较短的字符串
        for (int i = 0; i < min(lenS, lenT); ++i) {
            if (s[i] != t[i]) {
                // 找到不同字符后的判断逻辑
                if (lenS == lenT) {
                    // 长度相等：替换操作，检查剩余子串是否相同
                    return s.substr(i + 1) == t.substr(i + 1);
                } else if (lenS < lenT) {
                    // s 较短：插入操作到 s，检查 s 当前及之后 vs t 下一个及之后
                    // 即 s[i...] == t[i+1...]
                    return s.substr(i) == t.substr(i + 1);
                } else {
                    // s 较长：删除操作 from s，检查 s 下一个及之后 vs t 当前及之后
                    // 即 s[i+1...] == t[i...]
                    return s.substr(i + 1) == t.substr(i);
                }
            }
        }
        
        // 如果循环结束未返回，说明前缀完全相同
        // 此时只有长度差为1才符合题意（例如 "a" 和 "ab"）
        return abs((int)(lenS - lenT)) == 1;
    }
};

复杂度分析

• 时间复杂度：O(N)，其中 N 是两个字符串中较短者的长度。我们需要遍历字符串进行比较。
• 空间复杂度：O(1)（如果不考虑字符串截取产生的临时对象）或 O(N)（取决于语言中 substr 的实现，C++ 中通常会产生新字符串副本）。上述代码中使用了 substr，因此实际空间复杂度可能随实现略有增加，但逻辑上是线性的。

总结

这道题的关键在于理清三种编辑操作的本质，并利用长度差提前剪枝。解法二通过统一处理流程，避免了繁琐的条件分支，是更推荐的实现方式。以上就是C++实现LeetCode(161.一个编辑距离)的详细内容，更多关于C++ LeetCode算法的资料请关注本站其它相关文章！