谷歌（Google）历年编程真题——相隔为 1 的编辑距离

本文主要是介绍谷歌（Google）历年编程真题——相隔为 1 的编辑距离，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

谷歌历年面试真题——数组和字符串系列真题练习。

相隔为 1 的编辑距离

给定两个字符串 s 和 t ，如果它们的编辑距离为 1 ，则返回 true ，否则返回 false 。
字符串 s 和字符串 t 之间满足编辑距离等于 1 有三种可能的情形：

往 s 中插入恰好一个字符得到 t
从 s 中删除恰好一个字符得到 t
在 s 中用一个不同的字符替换恰好一个字符得到 t

示例 1：

输入: s = “ab”, t = “acb”
输出: true
解释: 可以将 ‘c’ 插入字符串 s 来得到 t。

示例 2:

输入: s = “cab”, t = “ad”
输出: false
解释: 无法通过 1 步操作使 s 变为 t。

提示:

0 <= s.length, t.length <= 104
s 和 t 由小写字母，大写字母和数字组成

思路一：动态规划

可以使用动态规划来解决这个问题。定义一个二维数组 dp，其中 dp[i][j] 表示将字符串 s 的前 i 个字符转换成字符串 t 的前 j 个字符所需的最少操作次数。

动态规划的状态转移方程如下：

当 s[i-1] == t[j-1] 时，dp[i][j] = dp[i-1][j-1]，表示不需要进行任何操作。
否则，dp[i][j] 可以通过以下三种方式得到：
- 将 s 的前 i-1 个字符转换成 t 的前 j-1 个字符，然后在末尾插入一个字符，即 dp[i][j] = dp[i-1][j-1] + 1；
- 将 s 的前 i 个字符转换成 t 的前 j-1 个字符，然后删除一个字符，即 dp[i][j] = dp[i][j-1] + 1；
- 将 s 的前 i-1 个字符转换成 t 的前 j 个字符，然后替换一个字符，即 dp[i][j] = dp[i-1][j] + 1。

最终，如果 dp[m][n] == 1，则返回 True，否则返回 False，其中 m 是字符串 s 的长度，n 是字符串 t 的长度。

下面是相应的 Python 代码实现：

def isOneEditDistance(s: str, t: str) -> bool:m, n = len(s), len(t)if abs(m - n) > 1:return Falsedp = [[0] * (n + 1) for _ in range(m + 1)]for i in range(m + 1):dp[i][0] = ifor j in range(n + 1):dp[0][j] = jfor i in range(1, m + 1):for j in range(1, n + 1):if s[i - 1] == t[j - 1]:dp[i][j] = dp[i - 1][j - 1]else:dp[i][j] = min(dp[i - 1][j - 1], dp[i][j - 1], dp[i - 1][j]) + 1return dp[m][n] == 1# 示例测试
print(isOneEditDistance("ab", "acb"))  # 输出: True
print(isOneEditDistance("cab", "ad"))  # 输出: False

这样，通过动态规划求解编辑距离，判断是否为 1 即可。

思路二：双指针

另一种解题思路是利用双指针来比较两个字符串。首先判断两个字符串的长度，如果它们的长度相差大于1，则编辑距离必定大于1，直接返回 False。

然后，我们分别用指针 i 和 j 遍历字符串 s 和 t。当 s[i] != t[j] 时，有以下几种情况：

如果两个字符串长度相等，则我们只能通过修改其中一个字符来使得两个字符串相等，此时我们将 i 和 j 同时右移一位，继续比较后面的字符。
如果 s 的长度比 t 的长度长1，则说明只能通过删除 s[i] 来使得两个字符串相等，此时我们将 i 右移一位，继续比较后面的字符。
如果 s 的长度比 t 的长度短1，则说明只能通过删除 t[j] 来使得两个字符串相等，此时我们将 j 右移一位，继续比较后面的字符。

如果以上情况都不满足，则说明编辑距离大于1，返回 False。如果遍历完成后都没有返回 False，则说明编辑距离为1，返回 True。

下面是相应的 Python 代码实现：

def isOneEditDistance(s: str, t: str) -> bool:m, n = len(s), len(t)if abs(m - n) > 1:return Falsei, j = 0, 0edited = Falsewhile i < m and j < n:if s[i] != t[j]:if edited:return Falseif m == n:i += 1j += 1elif m < n:j += 1else:i += 1edited = Trueelse:i += 1j += 1if i < m or j < n:edited = Truereturn edited# 示例测试
print(isOneEditDistance("ab", "acb"))  # 输出: True
print(isOneEditDistance("cab", "ad"))  # 输出: False