LeetCode 161. One Edit Distance

Description

https://leetcode.com/problems/one-edit-distance/

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.

Example 3:

Input: s = "a", t = ""
Output: true

Example 4:

Input: s = "", t = "A"
Output: true

Constraints:

• 0 <= s.length <= 104
• 0 <= t.length <= 104
• s and t consist of lower-case letters, upper-case letters and/or digits.

Explanation

In order to have only one edit distance, s and t should only have the same length or have one length difference. When their lengths are the same, s and t should have only one character difference. When their length differences are one, check if the longer string can remove one character to be the shorter string.

Python Solution

class Solution:
    def isOneEditDistance(self, s: str, t: str) -> bool:
        if s == t:
            return False

        if abs(len(s) - len(t)) > 1:
            return False

        if abs(len(s) - len(t)) == 0:
            diff_count = 0

            for c1, c2 in zip(s, t):
                if c1 != c2:
                    diff_count += 1

            if diff_count > 1:
                return False
            else:
                return True
        else:
            long = s if len(s) > len(t) else t
            short = t if len(s) > len(t) else s

            for i in range(len(long)):
                after_delete = long[:i] + long[i+1:]

                if after_delete == short:
                    return True

            return False