面试题 01.05. 一次编辑
题目描述
字符串有三种编辑操作:插入一个字符、删除一个字符或者替换一个字符。 给定两个字符串，编写一个函数判定它们是否只需要一次(或者零次)编辑。
示例 1:
输入:
first = “pale”
second = “ple”
输出: True
示例 2:
输入:
first = “pales”
second = “pal”
输出: False
答案
我的答案
class Solution { public boolean oneEditAway(String first, String second) { // 判断是否相同 if (first.equals(second)){ return true; } int f = first.length(); int c = second.length(); // 如果长度差大于1返回false if (Math.abs(f-c)>1){ return false; }else if (Math.abs(f-c)==1){ // 如果长度差等于1 int j = 0; int x = 0; // 如果f大于c if (f>c){ for (int i = 0; i < second.length(); i++) { if (second.charAt(i)!=first.charAt(j)){ i--; x++; } if (x>1){ return false; } j++; } }else { for (int i = 0; i < first.length(); i++) { if (second.charAt(j)!=first.charAt(i)){ i--; x++; } if (x>1){ return false; } j++; } } return true; }else { // 如果f等于c int j = 0; for (int i = 0; i < first.length(); i++) { if (first.charAt(i)!=second.charAt(i)){ j++; } if (j>1){ return false; } } return true; } } }
官方答案
分情况讨论
假设字符串 first 和 second 的长度分别是 m 和 n。
如果 first 和 second 需要一次编辑，则可能有三种情况：
往 first 中插入一个字符得到 second，此时 n−m=1，second 比 first 多一个字符，其余字符都相同；
从 first 中删除一个字符得到 second，此时 m−n=1，first 比 second 多一个字符，其余字符都相同；
将 first 中的一个字符替换成不同的字符得到 second，此时 m=n，first 和 second 恰好有一个字符不同。
如果 first 和 second 需要零次编辑，则 m=n 且 first 和 second 相等。
根据上述分析，当符合一次编辑时，first 和 second 的长度关系可能有三种情况，分别是 n−m=1、m−n=1 和 m=n。首先计算 first 和 second 的长度关系，在可能的三种情况中找到对应的一种情况，然后遍历字符串判断是否符合一次编辑或零次编辑。特别地，只有当 m=n 时才需要判断是否符合零次编辑。
如果长度关系不符合上述三种情况，即 ∣m−n∣>1，则不符合一次编辑或零次编辑。
具体实现方法如下。
当 n−m=1 或 m−n=1 时，由于两种情况具有对称性，因此可以定义一个函数统一计算这两种情况。用 longer 表示较长的字符串，shorter 表示较短的字符串，同时遍历两个字符串，比较对应下标处的字符是否相同，如果字符相同则将两个字符串的下标同时加 1，如果字符不同则只将 longer 的下标加 1。遍历过程中如果出现两个字符串的下标之差大于 1 则不符合一次编辑，遍历结束时如果两个字符串的下标之差不大于 1 则符合一次编辑。
当 m=n 时，同时遍历 first 和 second，比较相同下标处的字符是否相同。如果字符不同的下标个数不超过 1，则符合一次编辑或零次编辑。
代码：
class Solution { public boolean oneEditAway(String first, String second) { int m = first.length(), n = second.length(); if (n - m == 1) { return oneInsert(first, second); } else if (m - n == 1) { return oneInsert(second, first); } else if (m == n) { boolean foundDifference = false; for (int i = 0; i < m; i++) { if (first.charAt(i) != second.charAt(i)) { if (!foundDifference) { foundDifference = true; } else { return false; } } } return true; } else { return false; } } public boolean oneInsert(String shorter, String longer) { int length1 = shorter.length(), length2 = longer.length(); int index1 = 0, index2 = 0; while (index1 < length1 && index2 < length2) { if (shorter.charAt(index1) == longer.charAt(index2)) { index1++; } index2++; if (index2 - index1 > 1) { return false; } } return true; } }
复杂度分析
时间复杂度：O(m+n)，其中 m 和 n 分别是字符串 first 和 second 的长度。当 ∣m−n∣≤1 时，需要遍历两个字符串各一次。
空间复杂度：O(1)。
