Topic describes

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

 

Example 1:

Input: first = "pale" second = "ple" Output: TrueCopy the code

 

Example 2:

First = "pales" second = "Pal" Output: FalseCopy the code

solution

Double pointer.

If diff is greater than 1, return false.

Then we start traversing the two strings. First [I] is not the same as second[j].

  • ifdiff == 1,i++
  • ifdiff == -1,j++
  • ifdiff == 0,i++.j++

Op minus 1.

If I and j point to the same character, then I ++, j++.

Check whether the number of remaining edits is less than 0. If yes, false is not met.

At the end of the traversal, return true.

Python3

class Solution: def oneEditAway(self, first: str, second: str) -> bool: n1, n2 = len(first), len(second) diff = n1 - n2 if abs(diff) > 1: return False i, j, op = 0, 0, 1 while i < n1 and j < n2: not_same = first[i] ! = second[j] if not_same: if diff == 1: i += 1 elif diff == -1: j += 1 else: i += 1 j += 1 op -= 1 else: i += 1 j += 1 if op < 0: return False return TrueCopy the code

Java

class Solution {
    public boolean oneEditAway(String first, String second) {
        int n1 = first.length(), n2 = second.length();
        int diff = n1 - n2;
        if (Math.abs(diff) > 1) {
            return false;
        }
        int op = 1;
        for (int i = 0, j = 0; i < n1 && j < n2; ++i, ++j) {
            boolean notSame = first.charAt(i) != second.charAt(j);
            if (notSame) {
                if (diff == 1) {
                    // --j, ++i, ++j => ++i
                    --j;
                } else if (diff == -1) {
                    // --i, ++i, ++j => ++j
                    --i;
                }
                --op;
            }
            if (op < 0) {
                return false;
            }
        }
        return true;
    }
}
Copy the code

C++

class Solution {
public:
    bool oneEditAway(string first, string second) {
        int n1 = first.size(), n2 = second.size();
        int diff = n1 - n2;
        if (abs(diff) > 1) {
            return false;
        }
        int op = 1;
        for (int i = 0, j = 0; i < n1 && j < n2; ++i, ++j) {
            bool notSame = first[i] != second[j];
            if (notSame) {
                if (diff == 1) {
                    --j;
                } else if (diff == -1) {
                    --i;
                }
                --op;
            }
            if (op < 0) {
                return false;
            }
        }
        return true;
    }
};
Copy the code