Check if edit distance between two strings is one in Python

Suppose we have two strings s and t. We have to check whether the edit distance between s and t is exactly one or not. Here edit between two strings means any of these three −

• Insert a character
• Delete a character
• Replace a character

So, if the input is like s = "hello" t = "heillo", then the output will be True as we need to insert one character into s to get t.

To solve this, we will follow these steps −

• if |size of s - size of t| > 1, then
  • return false
• edit_dist_cnt := 0, i := 0, j := 0
• while i < size of s and j < size of t, do
  • if s[i] is not same as t[j], then
    • if edit_dist_cnt is same as 1, then
      • return false
    • if size of s > size of t, then
      • i := i + 1
    • otherwise when size of s < size of t, then
      • j := j + 1
    • otherwise,
      • i := i + 1, j := j + 1
    • edit_dist_cnt := edit_dist_cnt + 1
  • otherwise,
    • i := i + 1, j := j + 1
• if i < size of s or j < size of t, then
  • edit_dist_cnt := edit_dist_cnt + 1
• return true when edit_dist_cnt is same as 1, otherwise false

Example

Let us see the following implementation to get better understanding −

 Live Demo

def solve(s, t):    if abs(len(s) - len(t)) > 1:       return false    edit_dist_cnt = 0    i = 0    j = 0    while i < len(s) and j < len(t):       if s[i] != t[j]:          if edit_dist_cnt == 1:             return false          if len(s) > len(t):             i += 1          elif len(s) < len(t):             j += 1          else:             i += 1             j += 1          edit_dist_cnt +=1       else:          i += 1          j += 1    if i < len(s) or j < len(t):       edit_dist_cnt += 1    return edit_dist_cnt == 1 s = "hello" t = "heillo" print(solve(s, t))

Input

"hello", "heillo"

Output

True