Advertisement
viligen

minimum_edit_dist_DP

Aug 10th, 2022
541
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
Python 0.72 KB | None | 0 0
  1. replacement_cost = int(input())
  2. insert_cost = int(input())
  3. del_cost = int(input())
  4. first = input()
  5. second = input()
  6.  
  7. rows = len(first) + 1
  8. cols = len(second) + 1
  9.  
  10. dp = [[0] * cols for _ in range(rows)]
  11.  
  12. for col in range(1, cols):
  13.     dp[0][col] = dp[0][col-1] + insert_cost
  14. for row in range(1, rows):
  15.     dp[row][0] = dp[row-1][0] + del_cost
  16.  
  17. for row in range(1, rows):
  18.     for col in range(1, cols):
  19.         if first[row-1] == second[col-1]:
  20.             dp[row][col] = dp[row-1][col-1]
  21.         else:
  22.             dp[row][col] = min(dp[row-1][col-1] + replacement_cost,
  23.                                dp[row-1][col] + del_cost, dp[row][col-1]+insert_cost)
  24.  
  25. print(f'Minimum edit distance: {dp[rows-1][cols-1]}')
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement