算法题--求两个字符串的距离

image.png

0. 链接

题目链接

1. 题目

Given two words word1 and word2, find the minimum number of operations required to convert word1 to word2.

You have the following 3 operations permitted on a word:

Insert a character
Delete a character
Replace a character
Example 1:

Input: word1 = "horse", word2 = "ros"
Output: 3
Explanation: 
horse -> rorse (replace 'h' with 'r')
rorse -> rose (remove 'r')
rose -> ros (remove 'e')

Example 2:

Input: word1 = "intention", word2 = "execution"
Output: 5
Explanation: 
intention -> inention (remove 't')
inention -> enention (replace 'i' with 'e')
enention -> exention (replace 'n' with 'x')
exention -> exection (replace 'n' with 'c')
exection -> execution (insert 'u')

2. 思路1：动态规划

• 首先想到通过调整a使其跟b相同时, 假设只差最后一个字母待确定的话，则a相比b只有三种可能情况:
  • 情况1: a比b多一个字母
  • 情况2: a比b少一个字母
  • 情况3: a和b前面字母都相同，只剩最后一个字母有区别
• 很容易想起动态规划，假设dp[i][j]表示a[0: i + 1]通过调整得到b[0: j + 1]所需要的步数
  则有

如果a[i] == b[j] 则
    dp[i][j] = dp[i - 1][j - 1]
否则
    dp[i][j] = 1 + min(
                dp[i - 1][j], # 表示情况1
                dp[i][j - 1] # 表示情况2
                dp[i - 1][j - 1] # 表示情况3
            )

初始条件为:

dp[i][0] = i
dp[0][j] = j

3. 代码

# coding:utf8

class Solution:
    def minDistance(self, word1: str, word2: str) -> int:
        if word1 is None or word2 is None:
            return -1

        m, n = len(word1), len(word2)
        if m == 0:
            return n
        if n == 0:
            return m

        dp = [[0] * (n + 1) for _ in range(m + 1)]
        for i in range(m + 1):
            dp[i][0] = i
        for j in range(n + 1):
            dp[0][j] = j
        for i in range(1, m + 1):
            for j in range(1, n + 1):
                if word1[i - 1] == word2[j - 1]:
                    dp[i][j] = dp[i - 1][j - 1]
                else:
                    delete = dp[i - 1][j]
                    insert = dp[i][j - 1]
                    replace = dp[i - 1][j - 1]
                    dp[i][j] = min(delete, min(insert, replace)) + 1

        return dp[m][n]


def test(solution, a, b):
    print('a={}, b={} => {}'.format(a, b, solution.minDistance(a, b)))


solution = Solution()
test(solution, 'horse', 'ros')
test(solution, 'intention', 'execution')
test(solution, 'distance', 'springbok')

输出结果

a=horse, b=ros => 3
a=intention, b=execution => 5
a=distance, b=springbok => 9

4. 结果

image.png