fork(4) download
copy 
  1. def lev(s1, s2):
  2.     if len(s1) < len(s2):
  3.         return lev(s2, s1)
  4.  
  5.     # len(s1) >= len(s2)
  6.     if len(s2) == 0:
  7.         return len(s1)
  8.  
  9.     previous_row = range(len(s2) + 1)
  10.     for i, c1 in enumerate(s1):
  11.         current_row = [i + 1]
  12.         for j, c2 in enumerate(s2):
  13.             insertions = previous_row[j + 1] + 1 # j+1 instead of j since previous_row and current_row are one character longer
  14.             deletions = current_row[j] + 1       # than s2
  15.             substitutions = previous_row[j] + (c1 != c2)
  16.             current_row.append(min(insertions, deletions, substitutions))
  17.         previous_row = current_row
  18.  
  19.     return previous_row[-1]
  20.  
  21. s1=raw_input()
  22. s2=raw_input()
  23.  
  24. def printAllLevSteps(s1, s2):
  25.     if len(s1) < len(s2):
  26.         s1, s2 = s2, s1
  27.     chars = set(s2)
  28.     while s1 != s2:
  29.         oldS1 = s1
  30.         for i in range(len(s1)*2):
  31.             temp = list(s1)
  32.             if i % 2 == 0:
  33.                 del(temp[i/2]) #Remove char #i from temp
  34.             temp = "".join(temp)
  35.             if lev(temp, s2) < lev(s1, s2):
  36.                 s1 = temp
  37.                 break
  38.             if s1 != oldS1: # For some reason before the loop wouldn't stop
  39.                 break       # so I added this and now it's fine. Don't ask.
  40.             for char in chars:
  41.                 temp = list(s1)      # Make it into a list
  42.                 temp[i/2] = char       # Make char #i to variable char
  43.                 temp = "".join(temp) # Convert it to a string
  44.                 if lev(temp, s2) < lev(s1, s2):
  45.                     s1 = temp
  46.                     break
  47.         print s1
  48.  
  49. print "Distance:",lev(s1, s2)
  50. print "Steps:"
  51. printAllLevSteps(s1, s2)
  52.  
Success #stdin #stdout 0.02s 7696KB
comments (?)
stdin
copy 
CATURDAI
sunday
stdout
copy 
Distance: 8
Steps:
ATURDAI
TURDAI
sURDAI
suRDAI
sunDAI
sundAI
sundaI
sunday
https://ideone.com/w5zhpz
language:
Python (cpython 2.7.16)
created:
8 years ago
visibility:
public

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!