Advertisement
viligen

word_diff_DP

Aug 10th, 2022
481
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
Python 0.50 KB | None | 0 0
  1. first = input()
  2. second = input()
  3.  
  4. rows = len(first) +1
  5. cols = len(second) +1
  6.  
  7. dp = [[0] * cols for _ in range(rows)]
  8.  
  9. for col in range(1, cols):
  10.     dp[0][col] = col
  11. for row in range(1, rows):
  12.     dp[row][0] = row
  13.  
  14. for row in range(1, rows):
  15.     for col in range(1, cols):
  16.         if first[row-1] == second[col-1]:
  17.             dp[row][col] = dp[row-1][col-1]
  18.         else:
  19.             dp[row][col] = min(dp[row][col-1], dp[row-1][col]) + 1
  20.  
  21. print('Deletions and Insertions:', dp[rows-1][cols-1])
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement