output_description: Print the edit distance in a line.
input_description: s1
      s2
      
  
  Two words s1 and s2 are given in the first line and the second line
  respectively. The words will consist of lower case characters.
attempt: def main():
      X = input()
      Y = input()
      dp = []
      for y in range(len(Y)):
          now = 0
          for i in range(len(dp)):
              d = dp[i]
              if Y[y] in X[now:d]:
                  dp[i] = now + X[now:d].index(Y[y])
              now = d + 1
          if Y[y] in X[now:]:
              dp.append(now + X[now:].index(Y[y]))
      return max(len(X), len(Y)) - len(dp)
  
  
  print(main())
  
problem_description: Edit Distance (Levenshtein Distance)
  
    
  
  Find the edit distance between given two words s1 and s2.
  
  The disntace is the minimum number of single-character edits required to
  change one word into the other. The edits including the following operations:
  
    * **insertion** : Insert a character at a particular position.
    * **deletion** : Delete a character at a particular position. 
    * **substitution** : Change the character at a particular position to a different character
samples: [{"input": "acac\n    acm", "output": "2"}, {"input": "icpc\n    icpc", "output": "0"}]