72. Edit Distance
- Total Accepted: 71110
- Total Submissions: 236049
- Difficulty: Hard
- Contributors: Admin
Given two words word1 and word2, find the minimum number of steps required to convert word1 to word2. (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
Code
class Solution(object):
def minDistance(self, word1, word2):
"""
:type word1: str
:type word2: str
:rtype: int
"""
d = [[0]*(len(word2)+1) for i in xrange(len(word1)+1)]
for i in xrange(len(word1)+1):
d[i][0] = i
for j in xrange(len(word2)+1):
d[0][j] = j
for i in xrange(1, len(word1)+1):
for j in xrange(1, len(word2)+1):
if word1[i-1] == word2[j-1]:
d[i][j] = d[i-1][j-1]
else:
d[i][j] = min(d[i-1][j]+1, # delete word1[i]
d[i][j-1]+1, # delete word2[j]
d[i-1][j-1]+1 # replace word1[i] by word2[j]
)
return d[-1][-1]
Idea
We maintain a 2D array d, where d[i][j] means the edit distance between the substring word1[:i] and word2[:j].
Code
class Solution(object):
def minDistance(self, word1, word2):
"""
:type word1: str
:type word2: str
:rtype: int
"""
d = [i for i in xrange(len(word1)+1)]
for j in xrange(1, len(word2)+1):
pre = d[0]
d[0] = j
for i in xrange(1, len(word1)+1):
if word1[i-1] == word2[j-1]:
d[i], pre = pre, d[i]
else:
d[i], pre = min(d[i-1]+1, # delete word1[i]
d[i]+1, # delete word2[j]
pre+1 # replace word1[i] by word2[j]
), d[i]
return d[-1]
Idea
Convert the 2D DP matrix into 1D. pre is the value of d[i-1][j-1] when d is 2D.
Reference
https://discuss.leetcode.com/topic/17639/20ms-detailed-explained-c-solutions-o-n-space