161. One Edit Distance

Given two stringss andt, determine if they are both one edit distance apart.

Note:

There are 3 possiblities to satisify one edit distance apart:

  1. Insert a character into s to get t
  2. Delete a character from s _to get t_
  3. Replace a character of s _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 = "cab", t = "ad"

Output: false

Explanation: We cannot get t from s by only one step.

Example 3:

Input:s = "1203", t = "1213"

Output: true

Explanation: We can replace '0' with '1' to get t.

Thoughts:

  1. Compare the string until first no equal char meet:
    1. return a[i+1:] == b[i:] # for deleteing ith element in a (assume a is longer than b)
    2. return a[i+1:] == b[i+1] # for replacing one to the other
    3. if two strings are equal in min(len(a),len(b)) return whether the distance is within 1 # for insert shorter one the last element from the longer one at the end

Code


class Solution(object):
    def isOneEditDistance(self, s, t):
        """
        :type s: str
        :type t: str
        :rtype: bool
        """
        m, n = len(s), len(t)


        for i in range(min(m,n)):
            if s[i] != t[i]:
                if m > n:
                    return s[i+1:] == t[i:] #  delete s[i]
                elif m == n:
                    return s[i+1:] == t[i+1:] # replace 
                else:
                    return s[i:] == t[i+1:] #  delete t[i]

        return abs(m - n) == 1

results matching ""

    No results matching ""