LeetCode_ Interview question 01.05 One edit

LeetCode_ Interview question 01.05 Primary edit [medium]

Topic:

Title:

There are three editing operations for Strings: insert a character, delete a character, or replace a character.
Given two strings, write a function to determine whether they require only one (or zero) edit.

Example 1:

input:
first = "pale"
second = "ple"
output: True

Example 2:

input:
first = "pales"
second = "pal"
output: False

Source: LeetCode_ Interview question 01.05 One edit

Problem solving ideas:

Methods: discuss according to the situation

Ideas and algorithms:

We can judge whether the first edit is required or whether the second edit is required. For this topic, we need to discuss it by situation.
Let the length of the strings first and second be m and n respectively.
According to the meaning of the question, if first and second need to be edited once, there are three situations:

  1. When m - n = 1, it indicates that first has one more character than second. You need to delete one character from the string first to get the string second (premise: other characters are the same);
  2. When n - m = 1, it indicates that second is one more character than first. You need to insert a character into the string first to get the string second (premise: other characters are the same);
  3. When m = n, it indicates that first and second have the same length and only one character is different. You need to replace one character in the string first to get second.

If first and second need zero edits, m = n and first and second need to be equal.
According to the above analysis, we know that there are three cases of the length relationship between first and second according to one edit: n - m = 1, m - n = 1 and m = n.
Then, we can first calculate the length relationship between first and second, find the corresponding one of the three possible cases, and then traverse the string to judge whether it conforms to one edit or zero edit.
It should be noted that only when m = n, it is necessary to determine whether it conforms to zero editing.
If the length relationship does not meet the above three conditions, i.e. | m - n | > 1, it does not meet one edit or zero edit.
The specific implementation method is as follows:

  1. When n - m = 1 or m - n = 1, because the two cases have symmetry, a function can be defined to calculate the two cases uniformly. Use long to represent a longer string and short to represent a shorter string. Traverse the two strings at the same time and compare whether the characters at the corresponding subscripts are the same. If the characters are the same, add 1 to the subscripts of the two strings at the same time. If the characters are different, only add 1 to the subscripts of long. During the traversal, if the difference between the subscripts of two strings is greater than 1, it does not meet the one-time editing. At the end of the traversal, if the difference between the subscripts of two strings is not greater than 1, it meets the one-time editing.
  2. When m = n, traverse first and second at the same time to compare whether the characters at the same subscript are the same. If the number of subscripts with different characters does not exceed 1, it meets one or zero edits.
The code is as follows (example):
class Solution {
    public boolean oneEditAway(String first, String second) {
        int m = first.length(), n = second.length();
        if(n - m == 1){
            return oneOperation(first, second);
        }else if(m - n == 1){
            return oneOperation(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 oneOperation(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;
    }
}

Execution time:

  • Execution time: 1 ms;
  • Memory consumption: 41.3 MB.

Industry is diligent and waste is playful; Actions come from thinking, but destruction comes from following—— Han Yu

Tags: Java Algorithm leetcode

Posted by Tyrant on Fri, 13 May 2022 23:56:30 +0300