161. One Edit Distance 🔒

Description

Given two strings s and t, return true if they are both one edit distance apart, otherwise return false.

A string s is said to be one distance apart from a string t if you can:

Insert exactly one character into s to get t.
Delete exactly one character from s to get t.
Replace exactly one character of s with a different character to get t.

Example 1:

Input: s = "ab", t = "acb"
Output: true
Explanation: We can insert 'c' into s to get t.

Example 2:

Input: s = "", t = ""
Output: false
Explanation: We cannot get t from s by only one step.

Constraints:

0 <= s.length, t.length <= 10⁴
s and t consist of lowercase letters, uppercase letters, and digits.

Solutions

Solution 1: Discuss Different Cases

Let \(m\) represent the length of string \(s\), and \(n\) represent the length of string \(t\). We can assume that \(m\) is always greater than or equal to \(n\).

If \(m-n > 1\), return false directly;

Otherwise, iterate through \(s\) and \(t\), if \(s[i]\) is not equal to \(t[i]\):

If \(m \neq n\), compare \(s[i+1:]\) with \(t[i:]\), return true if they are equal, otherwise return false;
If \(m = n\), compare \(s[i:]\) with \(t[i:]\), return true if they are equal, otherwise return false.

If the iteration ends, it means that all the characters of \(s\) and \(t\) that have been iterated are equal, at this time it needs to satisfy \(m=n+1\).

The time complexity is \(O(m)\), where \(m\) is the length of string \(s\). The space complexity is \(O(1)\).

Python3JavaC++GoTypeScript

class Solution:
    def isOneEditDistance(self, s: str, t: str) -> bool:
        if len(s) < len(t):
            return self.isOneEditDistance(t, s)
        m, n = len(s), len(t)
        if m - n > 1:
            return False
        for i, c in enumerate(t):
            if c != s[i]:
                return s[i + 1 :] == t[i + 1 :] if m == n else s[i + 1 :] == t[i:]
        return m == n + 1

class Solution {
    public boolean isOneEditDistance(String s, String t) {
        int m = s.length(), n = t.length();
        if (m < n) {
            return isOneEditDistance(t, s);
        }
        if (m - n > 1) {
            return false;
        }
        for (int i = 0; i < n; ++i) {
            if (s.charAt(i) != t.charAt(i)) {
                if (m == n) {
                    return s.substring(i + 1).equals(t.substring(i + 1));
                }
                return s.substring(i + 1).equals(t.substring(i));
            }
        }
        return m == n + 1;
    }
}

class Solution {
public:
    bool isOneEditDistance(string s, string t) {
        int m = s.size(), n = t.size();
        if (m < n) return isOneEditDistance(t, s);
        if (m - n > 1) return false;
        for (int i = 0; i < n; ++i) {
            if (s[i] != t[i]) {
                if (m == n) return s.substr(i + 1) == t.substr(i + 1);
                return s.substr(i + 1) == t.substr(i);
            }
        }
        return m == n + 1;
    }
};

func isOneEditDistance(s string, t string) bool {
    m, n := len(s), len(t)
    if m < n {
        return isOneEditDistance(t, s)
    }
    if m-n > 1 {
        return false
    }
    for i := range t {
        if s[i] != t[i] {
            if m == n {
                return s[i+1:] == t[i+1:]
            }
            return s[i+1:] == t[i:]
        }
    }
    return m == n+1
}

function isOneEditDistance(s: string, t: string): boolean {
    const [m, n] = [s.length, t.length];
    if (m < n) {
        return isOneEditDistance(t, s);
    }
    if (m - n > 1) {
        return false;
    }
    for (let i = 0; i < n; ++i) {
        if (s[i] !== t[i]) {
            return s.slice(i + 1) === t.slice(i + (m === n ? 1 : 0));
        }
    }
    return m === n + 1;
}

161. One Edit Distance 🔒

Description

Solutions

Solution 1: Discuss Different Cases

Comments