问题

给你两个单词 word1 和 word2，请你计算出将 word1 转换成 word2 所使用的最少操作数 。
你可以对一个单词进行如下三种操作：

  • 插入一个字符
  • 删除一个字符
  • 替换一个字符

示例：
输入：word1 = “horse”, word2 = “ros”
输出：3
解释：
horse -> rorse (将 ‘h’ 替换为 ‘r’)
rorse -> rose (删除 ‘r’)
rose -> ros (删除 ‘e’)

思路

动态规划问题，具有独立的子问题，设dp[i][j]为s1[0..i]和s2[0..j]的最小编辑距离，则
状态转移方程为：
编辑距离 - 图1
即对s1[0..i]和s2[0..j]的最后一个字符，可以做三种操作使之相同，距离分别加1，但当s1[i] == s2[j] 时，替换操作可以不需要，不用加1，然后三种操作取编辑距离最小的一个。
基本情况是当一个字符串为空时，编辑距离等于另一个字符串的长度。

代码

  1. pub fn min_distance(word1: String, word2: String) -> i32 {
  2.     let mut dp = vec![vec![0;word2.len() + 1];word1.len() + 1];
  3.     let s1 = word1.as_bytes();
  4.     let s2 = word2.as_bytes();
  6.     // base case
  7.     for i in 1..=word1.len() {
  8.         dp[i][0] = i as i32;
  9.     }
  11.     for i in 1..=word2.len() {
  12.         dp[0][i] = i as i32;
  13.     }
  15.     for i in 1..=word1.len() {
  16.         for j in 1..=word2.len() {
  17.             if s1[i-1] == s2[j-1] {
  18.                 // 字符相等可以什么也不做，或者插入和删除
  19.                 dp[i][j] = dp[i-1][j-1];
  20.             } else {
  21.                 // 字符不等可以替换，插入和删除
  22.                 dp[i][j] = dp[i-1][j-1] + 1;
  23.             }
  25.             // 删除和插入操作，对应4种情况
  26.             dp[i][j] = min(dp[i][j], dp[i-1][j] + 1);
  27.             dp[i][j] = min(dp[i][j], dp[i][j-1] + 1);
  28.         }
  29.     }
  31.     dp[word1.len()][word2.len()]
  32. }