Two pointer in python, scan from left to right


  • 0
    G

    The idea is use two pointer both scanning through whole string and to see if edit distance is less than or equal to 1.
    If s[s_p] != t[t_p], check s_p+1 and t_p+1 to line up next comparison.
    After while loop, because the length of s and t might be different, we need to compensate the difference.

    class Solution(object):
        def isOneEditDistance(self, s, t):
            """
            :type s: str
            :type t: str
            :rtype: bool
            """
            #corner case
            if not s and not t:
                return False
            #early end
            if abs(len(s) - len(t)) > 1:
                return False
            s_p, t_p, edit_dis = 0, 0, 0
            while s_p < len(s) and t_p < len(t):
                if s[s_p] != t[t_p]:
                    edit_dis += 1
                    if t_p+1 < len(t) and s[s_p] == t[t_p+1]:
                        t_p+=1
                    elif s_p+1 < len(s) and s[s_p+1] == t[t_p]:
                        s_p+=1
                if edit_dis > 1:
                    return False
                s_p+=1
                t_p+=1
            edit_dis += (len(s) - s_p) + (len(t) - t_p)
            return edit_dis == 1

Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.