编辑距离(一)

java版——动态规划
dp[i][j] 表示 str1 的前 i 个字符和 str2 的前 j 个字符的编辑距离。

(以下说的相等是指我们已经知道它们的编辑距离)

• 如果 str1 的前 i - 1 个字符和 str2 的前 j 个字符相等，那么我们只需要在 str1 最后插入一个字符就可以转化为 str2 。 dp[i][j] = dp[i - 1][j] + 1
• 如果 str1 的前 i 个字符和 str2 的前 j - 1 个字符相等，那么我们只需要在 str1 最后删除一个字符就可以转化为 str2 。 dp[i][j] = dp[i][j - 1] + 1
• 如果 str1 的前 i - 1 个字符和 str2 的前 j - 1 个字符相等，那么我们要判断 str1 和 str2 最后一个字符是否相等：
  • 如果相等，则不需要任何操作。 dp[i][j] = dp[i - 1][j - 1]
  • 如果不相等，则只需要将 str1 最后一个字符修改为 str2 最后一个字符即可。dp[i][j] = dp[i - 1][j - 1] + 1

最终 dp[i][j] 为上面三种状态的最小值：
dp[i][j] = min(dp[i - 1][j], dp[i][j - 1], dp[i - 1][j - 1]) + 1

奥，对了，我们还要考虑边界情况，当str1为空时，编辑距离就为str2的长度（str1依次插入str2个字符），当str2为空时编辑距离就为str1的长度（str1依次删除每个字符）。

import java.util.*;

public class Solution {

    public int editDistance (String str1, String str2) {
        // write code here
        int len1 = str1.length();
        int len2 = str2.length();
        if(len1 == 0 || len2 == 0){
            return len1 + len2;
        }
        int[][] dp = new int[len1 + 1][len2 + 1];
        for(int i = 0; i <= len1; i++){
            dp[i][0] = i;
        }
        for(int j = 0; j <= len2; j++){
            dp[0][j] = j;
        }
        for(int i = 1; i <= len1; i++){
            for(int j = 1; j <= len2; j++){
                if(str1.charAt(i - 1) == str2.charAt(j - 1)){
                    dp[i][j] = dp[i - 1][j - 1];
                }else{
                    dp[i][j] = Math.min(Math.min(dp[i - 1][j], dp[i][j - 1]), dp[i - 1][j - 1]) + 1;
                }
            }
        }
        return dp[len1][len2];
    }
}

public class Solution {
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     * 
     * @param str1 string字符串 
     * @param str2 string字符串 
     * @return int整型
     */
    public int editDistance (String str1, String str2) {
        int s1Len = str1.length();
        int s2Len = str2.length();
        // 如果有一个字符串长度等于0，那么最小变换次数即为 s1Len + s2Len;
        if(s1Len == 0 || s2Len == 0) return s1Len + s2Len;
        

        // 初始化dp数组，dp[i][j] 记录 str1 每一个字符 变成 str2的次数
        int[][] dp = new int[s1Len + 1][s2Len + 1]; // 第一行第一列，辅助单元格
        // 初始化第一行
        // 可以理解为: 将一个空串，转变为str2字符串从0 ~ i的字符 所需要的次数
        for (int i = 1; i < dp[0].length; i++) dp[0][i] = i;
        // 初始化第一列
        // 可以理解为: 将str1字符串从0 ~ i的字符 转变为 一个空串 所需要的次数
        for (int i = 1; i < dp.length; i++) dp[i][0] = i;

        // 下标从1开始遍历每一行
        for (int i = 1; i < dp.length; i++) {
            // 取出str1的 i索引字符
            char strChar1 = str1.charAt(i - 1);
            // 下标从1开始遍历每一列
            for (int j = 1; j < dp[0].length; j++) {
                // 取出str2的 j索引字符
                char strChar2 = str2.charAt(j - 1);
                // 如果相等，那么只需要取出左斜方单元格记录的次数即可
                if(strChar1 == strChar2){
                    dp[i][j] = dp[i - 1][j - 1];
                }else{
                    // 如果不相等，取出左斜方，上方，左方的值，取最小后 + 1 即为当前 0 ~ i索引的str1字符串变换成 0 ~ j索引的str2字符串所需要的次数
                    int i1 = dp[i - 1][j - 1];
                    int i2 = dp[i][j - 1];
                    int i3 = dp[i-1][j];
                    dp[i][j] = Math.min(i3, Math.min(i1, i2)) + 1;
                }
            }
        }

        // 循环结束，dp表格最后一个单元格记录的值，即为解
        return dp[s1Len][s2Len];
    }
}

class Solution {
public:
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     * 
     * @param str1 string字符串 
     * @param str2 string字符串 
     * @return int整型
     */
    int editDistance(string str1, string str2) {
        // 时间复杂度O(N^2)，空间复杂度O(N^2)
        int dp[str1.size() + 1][str2.size() + 1];
        for (int i = 0; i <= str1.size(); ++i) dp[i][0] = i;
        for (int j = 0; j <= str2.size(); ++j) dp[0][j] = j;
        for (int i = 1; i <= str1.size(); ++i) {
            for (int j = 1; j <= str2.size(); ++j) {
                if (str1[i - 1] == str2[j - 1]) dp[i][j] = dp[i - 1][j - 1];
                else dp[i][j] = min(dp[i - 1][j - 1], min(dp[i - 1][j], dp[i][j - 1])) + 1;
            }
        }
        return dp[str1.size()][str2.size()];
    }
};

#
# 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
#
# 
# @param str1 string字符串 
# @param str2 string字符串 
# @return int整型
#
class Solution:
    def editDistance(self , str1: str, str2: str) -> int:
        l1, l2 = len(str1) + 1, len(str2) + 1
        lev = [[0]*l2 for _ in range(l1)]
        for i in range(l1):
            lev[i][0] = i
        for i in range(l2):
            lev[0][i] = i
        for i in range(1, l1):
            for j in range(1, l2):
                tmp = lev[i-1][j-1] + (1 if str1[i-1] != str2[j-1] else 0)
                lev[i][j] = min(lev[i-1][j]+1, lev[i][j-1]+1, tmp)
        return lev[l1-1][l2-1]

class Solution:
    def editDistance(self , s1: str, s2: str) -> int:
        # write code here
        n1=len(s1)
        n2=len(s2)
        #dp[i+1][j+1]为s1[0..i]到s2[0...j]的最少操作数
        dp = [[0]*(n2+1) for _ in range(n1+1)]
        #确定初始值
        for j in range(n2+1):
            dp[0][j]=j
        for i in range(n1+1):
            dp[i][0]=i
        #状态转移
        for i in range(1,n1+1):
            for j in range(1,n2+1):
                if s1[i-1]==s2[j-1]:
                    dp[i][j]=dp[i-1][j-1]
                else:
                    #[i][j],由于i和j-1匹配，i处插得到新的i，至j匹配
                    #[i][j],由于i-1和j匹配，i处删，至i-1匹配
                    #替换,由于i-1和j-1匹配，i处替换成j
                    dp[i][j] = min(dp[i][j-1]+1,  \
                                   dp[i-1][j]+1,  \
                                   dp[i-1][j-1]+1)
        return dp[n1][n2]

 public int editDistance(String str1, String str2) {
        // write code here
        int m = str1.length();
        int n = str2.length();

        // 创建一个二维数组来存储编辑距离
        // dp[i][j] 表示将 str1 的前 i 个字符转换为 str2 的前 j 个字符所需的最少操作数。
        // dp[m] 就是 0~m-1 共m 个字符串，这里的m 理解为长度
        int[][] dp = new int[m + 1][n + 1];

        // dp[i][0] 表示将 str1 的前 i 个字符转换为空字符串所需的操作数,即删除操作的次数
        for (int i = 1; i <= m; i++) {
            dp[i][0] = i;
        }
        // 将空字符串转为 0~j-1 的字符串需要的次数
        for (int j = 1; j <= n; j++) {
            dp[0][j] = j;
        }

        // 初始化完成, 开始动态规划
        for (int i = 1; i <= m; i++) {
            for (int j = 1; j <= n; j++) {
                // 如果字符相同，则无需要转换
                if (str1.charAt(i - 1) == str2.charAt(j - 1)) {
                    dp[i][j] = dp[i - 1][j - 1];
                } else {
                    // 不相同分为三种情况，依赖动态规划数组取三者最小值
                    // 左比右多1，右+1，一步到位
                    int insert = dp[i][j - 1] + 1;
                    // 左比右少1，右减一，一步到位
                    int delete = dp[i - 1][j] + 1;
                    // 左右不一致，直接替换，也是一步到位
                    int replace = dp[i - 1][j - 1] + 1;
                    // 取最小值更新当前的状态数组
                    dp[i][j] = Math.min(insert, Math.min(delete, replace));
                }
            }
        }

        return dp[m][n];
    }

#include <vector>
class Solution {
public:
      int editDistance(string str1, string str2) {
        vector<vector<int>>d(str1.size()+1,vector<int>(str2.size()+1));
        for(int i=0;i<=str1.size();i++){
            d[i][0]=i;
        }
        for(int j=0;j<=str2.size();j++){
            d[0][j]=j;
        }
        for(int i=1;i<=str1.size();i++){
            for( int j=1;j<=str2.size();j++){
                if(str1[i-1]==str2[j-1]){
                    d[i][j]=d[i-1][j-1];
                }else{
                    d[i][j]=min(d[i-1][j-1],min(d[i-1][j],d[i][j-1]))+1;
                }
            }
        }
        return d[str1.size()][str2.size()];
    }
};

#define min(a,b) (a<b?a:b)
#define min3(a,b,c) (a<min(b,c)?a:min(b,c))
int editDistance(char* str1, char* str2 ) {
    int dp[1001][1001], i, j;
    for(i=1; i<=strlen(str1); i++) 
        dp[i][0] = i;
    for(i=1; i<=strlen(str2); i++) 
        dp[0][i] = i;
    for(i=1; i<=strlen(str1); i++) {
        for(j=1; j<=strlen(str2); j++) {
            if(str1[i-1]==str2[j-1]) 
                dp[i][j] = dp[i-1][j-1];
            else 
                dp[i][j] = min3(dp[i-1][j-1], dp[i-1][j], dp[i][j-1])+1;
        }
    }
    return dp[i-1][j-1];
}

/**
 * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
 *
 *
 * @param str1 string字符串
 * @param str2 string字符串
 * @return int整型
 */
export function editDistance(str1: string, str2: string): number {
    // write code here
    const m = str1.length;
    const n = str2.length;

    // 初始化 dp 数组
    const dp: number[][] = new Array(m + 1);
    for (let i = 0; i <= m; i++) {
        dp[i] = new Array(n + 1).fill(0);
    }

    // 初始化边界条件
    for (let i = 0; i <= m; i++) {
        dp[i][0] = i;
    }
    for (let j = 0; j <= n; j++) {
        dp[0][j] = j;
    }

    // 动态规划计算最少操作数
    for (let i = 1; i <= m; i++) {
        for (let j = 1; j <= n; j++) {
            if (str1.charAt(i - 1) === str2.charAt(j - 1)) {
                dp[i][j] = dp[i - 1][j - 1];
            } else {
                dp[i][j] = Math.min(
                    dp[i - 1][j - 1] + 1, // 修改字符
                    Math.min(
                        dp[i][j - 1] + 1, // 插入一个字符
                        dp[i - 1][j] + 1
                    )
                ); // 删除一个字符
            }
        }
    }

    return dp[m][n];
}

import java.util.*;


public class Solution {
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     * 
     * @param str1 string字符串 
     * @param str2 string字符串 
     * @return int整型
     */
    public int editDistance (String str1, String str2) {
        // write code here
        // 状态定义dp[i][j]：表示从两个字符串首部各自到str1[i]和str2[j]为止的字串需要的编辑距离，dp[str1.length][str2.length]就是要找的编辑距离
        int dp[][] = new int[str1.length() + 1][str2.length() + 1];

        // 初始化,当其中一个字符串为空时，只需其中一个字符串增加或删除对应位置字符即可，此时编辑距离+1
        for(int i = 1;i <= str1.length();i++){
            dp[i][0] = dp[i - 1][0] + 1;
        }

        for(int j = 1;j <= str2.length();j++){
            dp[0][j] = dp[0][j - 1] + 1;
        }

        // 状态转移：当str[i]和str2[j]字符相等时，则不需要编辑，编辑距离为dp[i - 1][j - 1]。否则最小编辑距离取决于由dp[i - 1][j - 1]、dp[i - 1][j]、dp[i][j - 1]经过编辑后的最小编辑距离
        for(int i = 1;i <= str1.length();i++){
            for(int j = 1;j <= str2.length();j++){
                if(str1.charAt(i - 1) == str2.charAt(j - 1)){
                    dp[i][j] = dp[i - 1][j - 1];
                }else{
                    dp[i][j] = Math.min(dp[i - 1][j - 1],Math.min(dp[i - 1][j],dp[i][j - 1])) + 1;
                }
            }
        }
        return dp[str1.length()][str2.length()];
    }
}

import java.util.*;


public class Solution {
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     * 
     * @param str1 string字符串 
     * @param str2 string字符串 
     * @return int整型
     */
    public int editDistance (String str1, String str2) {
        // write code here
        // dp[i][j] str1 的 0 - i 到 str2 0 -j最少操作次数
        // dp[i][j] 如果 str1.i == str2.j  ->  dp[i][j] = dp[i - 1][j - 1]
        // 如果不相等，看删除哪个，究竟删除str1的i还是删除str2的j或者直接将str1的i修改成str2的j，哪个需要次数小取哪个
        // dp[i][j] = Math.min(Math.min(dp[i][j - 1], dp[i - 1][j]), dp[i - 1][j - 1]) + 1
        int l1 = str1.length();
        int l2 = str2.length();
        int[][] dp = new int[l1 + 1][l2 + 1];
        for(int i = 0; i <= l1; i++) {
            dp[i][0] = i; 
        }
        for(int j = 0; j <= l2; j++) {
            dp[0][j] = j;
        }

        for(int i = 1; i <= l1; i++) {
            for(int j = 1; j <= l2; j++) {
                if(str1.charAt(i - 1) == str2.charAt(j - 1)) {
                    dp[i][j] = dp[i - 1][j - 1];
                } else {
                    dp[i][j] = Math.min(Math.min(dp[i][j - 1], dp[i - 1][j]), dp[i - 1][j - 1]) + 1;
                }
            }
        }
        return dp[l1][l2];
    }
}

#include "iostream"
#include "vector"
using namespace std;
//问题描述：把字符串s1转成字符串s2的最杀后编辑次数，编辑操作包括：增删改三种，用ed(P,T)表示把T转成P需要的最少次数（反过来理解也是一样的）
/*
问题分析：
首先开辟一个二维矩阵D作为编辑距离矩阵，其中Di,j表示将P的前i个字符变成T的前j个字符的最小编辑距离，即Di,j=ed（P0~i,T0~j），注意这里的i、j不是字符串的下标，而是位置，例如P1表示P的第一个字符，P0~2表示P的前两个字符，因此可以通过以下几种情况得到状态转移方程：
假设Pi与Tj是相对应的，则：
⑴若Pi=Tj,则Di,j=Di-1,j-1 + 0=Di-1,j-1
⑵若Pi≠Tj，则有：
①把Tj改成Pi，Di,j达到最小，Di,j=Di-1,j-1 + 1
②T0~j比P0~i长，Pi是空格，则把Tj删掉后Di,j达到最小，删掉后就变成Pi与Tj-1对应，所以有Di,j=Di,j-1 +1
③T0~j比P0~i短，Tj是空格，则在Tj后插入Pi 使得Di,j达到最小，这时Pi-1与Tj对应，所以有Di,j=Di-1,j + 1
*/
int min(int a,int b,int c)
{
    return (a<b?a:b)<c?(a<b?a:b):c;
}
int editDistance(string str1, string str2)
{
    int l1=str1.length();
    int l2=str2.length();
    vector<vector<int>> dp(l1+1,vector<int>(l2+1));
    //初始化dp矩阵
    for(int j=0;j<=l2;j++) dp[0][j]=j;//第0行,表示将str1的前0个字符串转成str2的前j个字符串，需要进行j次插入操作
    for(int i=0;i<=l1;i++) dp[i][0]=i;//第0列，表示将str1的前i个字符串转成str2的前0个字符串，需要进行i次删除操作
    //动态规划
    for(int i=1;i<=l1;i++)
    {
        for(int j=1;j<=l2;j++)
        {
            //注意字符串下标是从0开始的，所以需要减一
            if(str1[i-1]==str2[j-1]) dp[i][j]=dp[i-1][j-1];//相等的话就不需要编辑操作
            else dp[i][j]=min(dp[i-1][j],dp[i][j-1],dp[i-1][j-1])+1;//否则，编辑、增加、删除三种操作选一种
        }
    }
    return dp[l1][l2];
}
int main()
{
    string s1,s2;
    cin>>s1>>s2;
    cout<<editDistance(s1,s2);
    return 0;
}

class Solution:
    def editDistance(self, str1: str, str2: str) -> int:
        # write code here
        # 动态规划
        if not str1&nbs***bsp;not str2:
            return max(len(str1), len(str2))
        # dp[i][j]表示str1[:i]转为str2[:j]的最少操作数
        dp = [[0] * (len(str2) + 1) for _ in range(len(str1) + 1)]
        # 初始化第一列(str1删除)和第一行(str1插入)
        for i in range(len(str1) + 1):
            dp[i][0] = i
        for j in range(len(str2) + 1):
            dp[0][j] = j
        for i in range(1, len(str1) + 1):
            for j in range(1, len(str2) + 1):
                if str1[i - 1] == str2[j - 1]:
                    dp[i][j] = dp[i - 1][j - 1]
                # 如果不等，则需要进行修改dp[i-1][j-1]+1或删除dp[i-1][j]+1或插入dp[i][j-1]+1次操作
                else:
                    dp[i][j] = min(dp[i - 1][j - 1], dp[i - 1][j], dp[i][j - 1]) + 1
        return dp[-1][-1]

using System;
using System.Linq;
using System.Collections.Generic;

class Solution {
    string str1;
    string str2;
    int[,] memo;
    public int editDistance (string str1, string str2) {
        this.str1 = str1;
        this.str2 = str2;

        memo = new int[str1.Length, str2.Length];
        for (int i = 0; i < str1.Length; i++)
            for (int j = 0; j < str2.Length; j++)
                memo[i, j] = -1;

        return Distance(str1.Length - 1, str2.Length - 1);
    }

    //定义：str1[0,i] 到str2[0,j]的所需步数
    int Distance(int i, int j)
    {
        //BaseCase 空串
        if (i < 0) return j + 1;
        if (j < 0) return i + 1;
        if (memo[i, j] != -1) return memo[i, j];

        if (str1[i] == str2[j])
            memo[i, j] = Distance(i - 1, j - 1);
        else
            memo[i, j] = new int[]
            {
                // 观察角度：用str1去迎合str2，选最好的做法
                Distance(i - 1, j), //str1[0,i - 1]可以到str2[0,j] str1[i]多余，删除
                Distance(i - 1, j - 1), //str1[0,i - 1]可以到str2[0,j - 1] str1[i]改为str2[j]，修改
                Distance(i, j - 1), //str1[0,i]可以到str2[0,j - 1] str1[j]需要补上，增加
            }.Min() + 1;
        return memo[i, j];
    }
}

class Solution:
    def editDistance(self , str1: str, str2: str) -> int:
        m, n = len(str1), len(str2)
        dp = [[0 for _ in range(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(m):
            for j in range(n):
                if str1[i] == str2[j]:
                    dp[i+1][j+1] = dp[i][j]
                else:
                    dp[i+1][j+1] = min(dp[i][j+1], dp[i+1][j], dp[i][j]) + 1
        return dp[m][n]