Leetcode: One Edit Distance

One Edit Distance

Similar Problems:

Given two strings S and T, determine if they are both one edit distance apart.

Github: code.dennyzhang.com

Credits To: leetcode.com

Leave me comments, if you have better ways to solve.

## Blog link: https://code.dennyzhang.com/one-edit-distance
## Basic Ideas:
## Complexity: Time O(n), Space O(1)
class Solution(object):
    def isOneEditDistance(self, s, t):
        :type s: str
        :type t: str
        :rtype: bool
        len_s, len_t = len(s), len(t)
        if abs(len_s - len_t) >= 2: return False
        if len_s == len_t:
            count = 0
            for i in range(len_s):
                if s[i] != t[i]: count += 1
                if count > 1: return False
            return count == 1
            # Use recursive to simplify the logic
            if len_s<len_t: return self.isOneEditDistance(t, s)
            # s is longer
            offset = 0
            for i in range(len_t):
                if s[i+offset] != t[i]:
                    if offset == 1: return False
                    offset = 1
                    # catch up check
                    if s[i+offset] != t[i]: return False
            return True

Share It, If You Like It.

Leave a Reply

Your email address will not be published.