72. Edit Distance
Given two wordsword1andword2, find the minimum number of steps required to convertword1toword2. (each operation is counted as 1 step.)
You have the following 3 operations permitted on a word:
a) Insert a character
b) Delete a character
c) Replace a character
Solution:
- definition of each state
- formulation to next state
- initialization
- return
All others are easy except step 2.
See code for commented logic
class Solution(object):
def minDistance(self, word1, word2):
"""
:type word1: str
:type word2: str
:rtype: int
"""
rowNum = len(word1)
colNum = len(word2)
# initialization
dp = [[0] * (colNum+1) for row in range(rowNum + 1)]
for row in range(rowNum + 1):
dp[row][0] = row
for col in range(colNum + 1):
dp[0][col] = col
# formulation to next state
for row in range(rowNum):
for col in range(colNum):
# step 2
if word1[row] == word2[col]:
# if this new char is the same for words, then move diagonally with 0
dp[row + 1][col + 1] = dp[row][col]
else:
# if not the same, then it's the min of 3 directions (insert, replace, delete) + 1
dp[row + 1][col + 1] = min( dp[row][col], dp[row + 1][col], dp[row][col + 1]) + 1
return dp[-1][-1]