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():
      S = input()
      T = input()
      ns = len(S)
      nt = len(T)
  
      dp = [[0] * (nt + 1) for _ in [0] * (ns + 1)]
      for i in range(ns + 1):
          dp[i][0] = i
      for j in range(nt + 1):
          dp[0][j] = j
  
      di_1 = dp[0]
      for s, di in zip(S, dp[1:]):
          j = 0
          di_1j_1 = di_1[0]
          dij_1 = di[0]
          for t in T:
              j += 1
              if s == t:
                  dmin = di_1j_1
                  di_1j = di_1[j]
              else:
                  dmin = di_1j = di_1[j]
                  if dij_1 < dmin:
                      dmin = dij_1
                  if di_1j_1 < dmin:
                      dmin = di_1j_1
                  dmin += 1
              di[j] = dij_1 = dmin
              di_1j_1 = di_1j
          di_1 = di
  
      print(dp[-1][-1])
  
  
  if __name__ == "__main__":
      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"}]