Leetcode interview question 01.05: primary editing

Title Description

There are three editing operations for Strings ： Insert an English character 、 Delete an English character or replace an English character . Given two strings , Write a function to determine if they only need to be done once ( Or zero times ) edit .

Example

Example 1：
Input :
first = “pale”
second = “ple”
Output : True

Example 2：
Input :
first = “pales”
second = “pal”
Output : False

The problem solving process

Ideas and steps

（1） remember  m  by  first  Length of string , n  by  second  Length of string ;
（2） When  |m - n| > 1,  That is, the length difference between two strings is greater than or equal to  2  when ,  direct  return false,  Because it is impossible to make two strings equal with one or less edits ;
（3） For convenience ,  We need to make sure  first  The string is a shorter one ,  So when  second  Is longer than  first  when ,  Swap two strings ;
（4） Use  i  Traverse  first  character string , j  Traverse  second  character string , count  Used to record the number of operations ;
（5） If  i  and  j  The corresponding characters are equal ,  Move right at the same time ;
（6） If  i  and  j  Not equal and  m == n,  In this case, the two characters can be made equal by the replacement operation ,  So as to ensure that the two strings are equal ,  therefore  i  and  j  Move right at the same time ,  meanwhile  count  Self increasing  1;
（7） If  i  and  j  Not equal and  m ≠ n,  Because we promised  first  Is a shorter string ,  So at this time  m < n,  In this case, the two characters can be made equal by adding or deleting ,  So as to ensure that the two strings are equal ,  here , i  unchanged , j  Move right ,  meanwhile  count  Self increasing  1;
（8） The condition for traversal is  i < m && j < n && count <= 1,  At the end of the cycle  count  Less than or equal to  1  Just return the result 

Code display

public class OneEditAway {
    

    /** *  remember  m  by  first  Length of string , n  by  second  Length of string  *  When  |m - n| > 1,  That is, the length difference between two strings is greater than or equal to  2  when ,  direct  return false,  Because it is impossible to make two strings equal with one or less edits  *  For convenience ,  We need to make sure  first  The string is a shorter one ,  So when  second  Is longer than  first  when ,  Swap two strings  *  Use  i  Traverse  first  character string , j  Traverse  second  character string , count  Used to record the number of operations  *  If  i  and  j  The corresponding characters are equal ,  Move right at the same time  *  If  i  and  j  Not equal and  m == n,  In this case, the two characters can be made equal by the replacement operation ,  So as to ensure that the two strings are equal ,  therefore  i  and  j  Move right at the same time ,  meanwhile  count  Self increasing  1 *  If  i  and  j  Not equal and  m ≠ n,  Because we promised  first  Is a shorter string ,  So at this time  m < n,  In this case, the two characters can be made equal by adding or deleting ,  So as to ensure that the two strings are equal ,  here , i  unchanged , j  Move right ,  meanwhile  count  Self increasing  1 *  The condition for traversal is  i < m && j < n && count <= 1,  At the end of the cycle  count  Less than or equal to  1  Just return the result  **/

    public boolean oneEditAway(String first, String second) {
    
        if (first.length() == 0 || second.length() == 0) {
    
            return true;
        }
        int m = first.length();
        int n = second.length();
        if (Math.abs(m - n) > 1) {
    
            return false;
        }
        if (m > n) {
    
            //  Guarantee  first  Is the shorter one 
            return oneEditAway(second, first);
        }
        // i  control  first  The traversal 
        int i = 0;
        // j  control  second  The traversal 
        int j = 0;
        // count  Record the number of operations 
        int count = 0;
        while (i < m && j < n && count <= 1) {
    
            char firstChar = first.charAt(i);
            char secondChar = second.charAt(j);
            if (firstChar == secondChar) {
    
                //  If two characters are equal ,  Move right at the same time 
                i++;
                j++;
            } else {
    
                //  If two characters are not equal 
                if (m == n) {
    
                    //  It can only be a replacement operation 
                    count++;
                    i++;
                    j++;
                } else {
    
                    // m ≠ n,  Because it has been ensured that  first  For a shorter string ,  So at this time  m < n
                    //  Insert or delete operation 
                    j++;
                    count++;
                }
            }
        }
        return count <= 1;
    }

    public static void main(String[] args) {
    
        System.out.println(new OneEditAway().oneEditAway("palet", "palt"));
    }

}