Edit Distance

edit_distance.py

"""
https://scammingthecodinginterview.com
Week 7: Dynamic Programming
Problem: 1
"""
class Solution(object):

  def solve(self, a, b):
    n = len(a)
    m = len(b)

    dp = [
      [0 for j in range(0, m+1)]
      for i in range(0, n+1)
    ]

    for i in range(1, m+1):
      dp[0][i] = i

    for i in range(1, n+1):
      dp[i][0] = i

    for i in range(n):
      for j in range(m):

        if a[i] == b[j]:
          dp[i+1][j+1] = dp[i][j]
        else:
          dp[i+1][j+1] = min(
            1 + dp[i][j],
            min(1 + dp[i][j + 1],1 + dp[i + 1][j])
          )

    return dp[n][m]


if __name__ == "__main__":
  a = 'aaa'
  b = 'aa'

  ans = Solution().solve(a, b)

  print(ans)