问题描述
Given two strings word1 and word2, return the minimum number of operations required to convert word1 to word2.
You have the following three operations permitted on a word:
Insert a character
Delete a character
Replace a character
Example 1:
1 | Input: word1 = "horse", word2 = "ros" |
Example 2:
1 | Input: word1 = "intention", word2 = "execution" |
Constraints:
- 0 <= word1.length, word2.length <= 500
- word1 and word2 consist of lowercase English letters.
解题思路
方法1: 递归+memo数组
- 对于当前比较的两个字符
word1[i]
和word2[j]
,若二者相同,直接跳到下一个位置。 - 若不相同,有三种处理方法,首先是直接插入一个
word2[j]
,那么word2[j]
位置的字符就跳过了,接着比较word1[i]
和word2[j+1]
即可。第二个种方法是删除,即将word1[i]
字符直接删掉,接着比较word1[i+1]
和word2[j]
即可。第三种则是将word1[i]
修改为word2[j]
,接着比较word1[i+1]
和word[j+1]
即可。 - 需要去掉大量的重复计算,这里使用记忆数组
memo
来保存计算过的状态,这里的insert
,remove
,replace
仅仅是表示当前对应的位置分别采用了插入,删除,和替换操作,整体返回的最小距离,后面位置的还是会调用递归返回最小的,
1 | var minDistance = function(word1, word2) { |
- 时间复杂度:O(max(m,n))
- 空间复杂度:O(m*n)
方法2: dp
dp[i][j]
表示从word1
的前i个字符转换到word2
的前j个字符所需要的步骤。- 当
word1[i] == word2[j]
时,dp[i][j] = dp[i - 1][j - 1]
,其他情况时,dp[i][j]
是其左,左上,上的三个值中的最小值加1,其实这里的左,上,和左上,分别对应的增加,删除,修改操作.
1 | var minDistance = function(word1, word2) { |
- 时间复杂度:O(max(m,n))
- 空间复杂度:O(m*n)