leetcode
leetcode 2801 ~ 2850
一次编辑

一次编辑

难度:

标签:

题目描述

There are three types of edits that can be performed on strings: insert a character, remove a character, or replace a character. Given two strings, write a function to check if they are one edit (or zero edits) away.

 

Example 1:

Input: 
first = "pale"
second = "ple"
Output: True

Example 2:

Input: 
first = "pales"
second = "pal"
Output: False

代码结果

运行时间: 19 ms, 内存: 15.9 MB

/*
 * 使用Java Stream判断字符串是否只需要一次编辑。
 */

import java.util.stream.IntStream;

public class OneEditAwayStream {
    public static boolean isOneEditAway(String first, String second) {
        if (Math.abs(first.length() - second.length()) > 1) return false;
        String s1 = first.length() < second.length() ? first : second;
        String s2 = first.length() < second.length() ? second : first;
        long differences = IntStream.range(0, s1.length())
            .filter(i -> s1.charAt(i) != s2.charAt(i + (s2.length() > s1.length() ? 1 : 0)))
            .count();
        return differences <= 1;
    }

    public static void main(String[] args) {
        System.out.println(isOneEditAway("pale", "ple")); // True
        System.out.println(isOneEditAway("pales", "pal")); // False
    }
}

解释

方法:

该题解首先通过比较两个字符串的长度来确定较短和较长的字符串，并保证后续操作总是在长度小的字符串上进行。如果两个字符串的长度差超过1，则直接返回False，因为无法通过一次操作使二者相同。接着，根据两个字符串长度是否相等分别处理：如果长度相等，则通过比较每个对应位置的字符，统计不同字符的数量是否超过1；如果长度不相等（此时长度差为1），则通过一个偏移量ofs来比对较短字符串中的每个字符是否与较长字符串中的对应位置匹配，一旦发现不匹配，则增加偏移量，并检查是否超过1次编辑的机会。

时间复杂度:

O(n)

空间复杂度:

O(1)

代码细节讲解

🦆
在处理长度不相等的情况时，你是如何确保只通过单个偏移量`ofs`来正确处理插入或删除操作的？
▷
在处理长度不相等的情况下，我们的目标是通过一次插入或删除操作来使两个字符串相等。这里的关键是使用一个单一的偏移量`ofs`来模拟插入或删除操作的效果。当我们在比较过程中遇到第一个不匹配的字符时，增加偏移量`ofs`，这意味着我们跳过了较长字符串中的一个字符（模拟删除操作），或者跳过了较短字符串中的位置（模拟插入操作）。一旦`ofs`被增加过一次，后续的比较都是基于这个新的偏移进行的。如果再发现不匹配的情况，即`ofs`需要再次增加，这将意味着需要超过一次的编辑操作，因此返回False。这种方法保证了我们只通过一次编辑操作（插入或删除）的模拟来判断两个字符串的相似性。
🦆
当两个字符串长度相等时，你提到通过计数不同的字符来决定是否可以通过一次替换来修正，那么这种方法是否考虑了所有可能导致字符串不同的因素？
▷
当两个字符串长度相等时，通过计数不同字符的方法主要是判断是否可以通过一次替换操作使两个字符串相同。这种方法确实考虑了所有可能导致两个等长字符串不同的因素，因为任何不同点都会在字符比较中被计数。如果不同字符的数量超过1，意味着需要多于一次的替换，因此返回False。此方法有效地检测了是否只需要一次替换就能解决问题，因为它直接对应于字符串中不匹配字符的数量。
🦆
在算法中，如果长度差正好为1，为什么增加偏移量后不再检查之前已经比较过的字符，这样做的正确性如何保证？
▷
在长度差为1的情况下，如果在某一点上字符不匹配，并且我们增加了偏移量`ofs`，这意味着我们已经尝试通过跳过较长字符串的一个字符来模拟删除操作，或者跳过较短字符串的一个字符来模拟插入操作。一旦偏移量增加，之前比较过的字符已经被确认是相匹配的，因此不需要重新检查。这种方法的正确性在于，一旦我们应用了一次编辑操作（通过增加偏移量），后续的所有字符应当一一对应相匹配，否则就意味着需要更多的编辑，这将违反题目要求的只允许一次编辑。因此，这种方法确保了一旦发现第一次偏差后的所有字符都必须匹配，从而保证算法的正确性。

相关问题

水域大小求和路径