161.One Edit Distance

Tags: [edit_distance], [two_pointer]

Com: {fb}

Link: https://leetcode.com/problems/one-edit-distance/#/description

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

More clean solution:

class Solution(object):
    def isOneEditDistance(self, s, t):
        """
        :type s: str
        :type t: str
        :rtype: bool
        """
        if not s:
            return t is not None and len(t) == 1
        if not t:
            return s is not None and len(s) == 1
        if abs(len(s) - len(t)) > 1:
            return False

        if len(s) == len(t):
            return self.is_one_modify(s, t)
        else:
            return self.is_one_delete(s, t)

    def is_one_modify(self, s, t):
        diff_char_counter = 0
        for i in xrange(len(s)):
            if s[i] != t[i]:
                if diff_char_counter == 1:
                    return False
                diff_char_counter += 1

        return diff_char_counter == 1

    def is_one_delete(self, s, t):
        short_str = s if len(s) < len(t) else t
        long_str = s if len(s) > len(t) else t

        index = 0
        while index < len(short_str):
            if short_str[index] != long_str[index]:
                return short_str[index:] == long_str[index + 1:]
            index += 1

        return True

Note:

• Be careful that in the 'is_one_modify' function, we should return diff_char_counter == 1.
• Time complexity = O(min(len(s), len(t))).

Solution: Two Pointer

class Solution(object):
    def isOneEditDistance(self, s, t):
        """
        :type s: str
        :type t: str
        :rtype: bool
        """
        if not s:
            return t is not None and len(t) == 1
        if not t:
            return s is not None and len(s) == 1

        if len(s) == len(t):
            diff_char_counter = 0
            for i in xrange(len(s)):
                if s[i] != t[i]:
                    diff_char_counter += 1

                if diff_char_counter > 1:
                    return False

            return diff_char_counter == 1

        if abs(len(s) - len(t)) == 1:
            short_str = s if len(s) < len(t) else t
            long_str = s if len(s) > len(t) else t

            skip_counter = 0
            long_index = 0
            short_index = 0
            while short_index < len(short_str) and long_index < len(long_str):
                long_c = long_str[long_index]
                short_c = short_str[short_index]
                if long_c != short_c:
                    if skip_counter == 1:
                        return False

                    skip_counter += 1
                    long_index += 1
                else:
                    short_index += 1
                    long_index += 1

            return True

        return False

Revelation:

• One edit distance means, insert one char or delete one char or replace one char in one string, which can make this modified string equal to the other string.
• Think about the case s = 'abc', t = 'ac', how do we deal with this scenario. We keep two pointers, one is pointing to longer string, the other is pointing to the short one, if we find the char in the longer one not match the char in the shorter one, at most we allow to skip one char in the longer one.

Note:

• Time complexity = O(min(len(s), len(t))).