LeetCode 面试题 01.05. 一次编辑

Categories:

题目描述
思路分析
1. 解法一：双指针一次遍历（推荐）
相似题目

题目描述

✅ 面试题 01.05. 一次编辑

思路分析

解法一：双指针一次遍历（推荐）

核心思路：

两字符串长度差大于 1，直接返回 false。

用双指针遍历，遇到不同字符时：

若已发生过编辑，返回 false。

根据长度关系，跳过一个字符（替换或插入/删除）。

最后允许剩余一个字符差异。

复杂度分析：

时间复杂度：O(n)，其中 n 为较短字符串长度。

空间复杂度：O(1)。

class Solution {
    public boolean oneEditAway(String first, String second) {
        int m = first.length();
        int n = second.length();
        if (Math.abs(m - n) > 1) {
            return false;
        }

        int i = 0;
        int j = 0;
        int edits = 0;

        while (i < m && j < n) {
            if (first.charAt(i) == second.charAt(j)) {
                i++;
                j++;
                continue;
            }

            if (edits == 1) {
                return false;
            }
            edits++;

            if (m == n) {
                i++;
                j++;
            } else if (m > n) {
                i++;
            } else {
                j++;
            }
        }

        return true;
    }
}

func oneEditAway(first string, second string) bool {
	m, n := len(first), len(second)
	if m-n > 1 || n-m > 1 {
		return false
	}

	i, j := 0, 0
	edits := 0
	for i < m && j < n {
		if first[i] == second[j] {
			i++
			j++
			continue
		}

		if edits == 1 {
			return false
		}
		edits++

		if m == n {
			i++
			j++
		} else if m > n {
			i++
		} else {
			j++
		}
	}

	return true
}

相似题目

题目	难度	考察点
72. 编辑距离	困难	DP
161. 相隔为 1 的编辑距离	中等	双指针
583. 两个字符串的删除操作	中等	DP
392. 判断子序列	简单	双指针
680. 验证回文串 II	简单	双指针
409. 最长回文串	简单	计数

本文作者: HGNULB

本文链接: https://hgnulb.github.io/blog/2023/16636749