text: """72. Edit Distance"""
  
  class Solution(object):
      def minDistance(self, word1, word2):
          """
          :type word1: str
          :type word2: str
          :rtype: int
          """
          ####### Practice
          m = len(word1)
          n = len(word2)
          dp = [[0]*(n+1) for _ in range(m+1)]
  
          for i in range(m+1):
              dp[i][0] = i
          for j in range(n+1):
              dp[0][j] = j
          for i in range(m):
              for j in range(n):
                  if word1[i] == word2[j]:
                      dp[i+1][j+1] = dp[i][j]
                  else:
                      dp[i+1][j+1] = 1 + min(dp[i][j], dp[i+1][j], dp[i][j+1])
          return dp[-1][-1]
  
  
  
          #################
          m = len(word1)
          n = len(word2)
  
          dp = [[0]*(n+1) for _ in range(m+1)]
  
          for i in range(m+1):
              dp[i][0] = i
          for j in range(n+1):
              dp[0][j] = j
  
          for i in range(m):
              for j in range(n):
                  if word1[i] == word2[j]:
                      dp[i+1][j+1] = dp[i][j]
                  else:
                      dp[i+1][j+1] = 1 + min(dp[i][j], dp[i][j+1], dp[i+1][j])
  
          return dp[m][n]
  