题解 | #牛群编号变更#

知识点：

动态规划/编辑距离

分析：

首先题目中给出两个字符串，有两种操作可以进行：

1.在编号中插入一个字符

2.删除编号中的一个字符

使得a字符串变为字符串b，求变更的最小次数

状态表示：

• 状态表示：word1[1~i]变为word2[1~j]的操作次数的最小次数
• 状态属性：min，求最小次数

状态计算

• 计算f[i][j]，依次考虑两种操作方式：

1) 删除操作：把word1[i]删掉之后word1[1~i]和word2[1~j]匹配，所以之前要先做到word1[1~(i-1)]和word2[1~j]匹配， f[i-1][j] + 1

2) 插入操作：插入之后word1[i]与word2[j]完全匹配，所以插入的就是word2[j] ，那填之前word1[1~i]和word2[1~(j-1)]匹配，f[i][j-1] + 1

3) 如果word1 i == word2 j的话，不用修改，那么取最小值min(f[i][j], f[i-1][j-1])

关于初始化：

知识点：

动态规划/编辑距离

分析：

首先题目中给出两个字符串，有两种操作可以进行：

1.在编号中插入一个字符

2.删除编号中的一个字符

使得a字符串变为字符串b，求变更的最小次数

状态表示：

• 状态表示：word1[1~i]变为word2[1~j]的操作次数的最小次数
• 状态属性：min，求最小次数

状态计算

• 计算f[i][j]，依次考虑两种操作方式：

1) 删除操作：把word1[i]删掉之后word1[1~i]和word2[1~j]匹配，所以之前要先做到word1[1~(i-1)]和word2[1~j]匹配， f[i-1][j] + 1

2) 插入操作：插入之后word1[i]与word2[j]完全匹配，所以插入的就是word2[j] ，那填之前word1[1~i]和word2[1~(j-1)]匹配，f[i][j-1] + 1

3) 如果word1 i == word2 j的话，不用修改，那么取最小值min(f[i][j], f[i-1][j-1])

关于初始化：

1. f[0][i]如果word1初始长度就是0，那么只能用插入操作让它变成word2
2. f[i][0]同样地，如果word2的长度是0，那么word1只能用删除操作让它变成word2

编程语言：

C/C++/Go/Python

完整代码：

c++：

    int f[110][110];
    int minDistance(string word1, string word2) {
        int n = word1.size();
        int m = word2.size();
        for(int i =0;i<=n;i++) f[i][0] = i;
        for(int i =0;i<=m;i++) f[0][i] = i;
        for(int i = 1;i<=n;i++){
            for(int j = 1;j<=m;j++){
                f[i][j] = min(f[i][j - 1],f[i-1][j]) + 1;
                if(word1[i-1] == word2[j-1]) f[i][j] = min(f[i][j],f[i-1][j-1]);
            }
        }
        return f[n][m];
    }

C：

int f[510][510];
int minDistance(char * word1, char * word2){
    int n = strlen(word1);
    int m = strlen(word2);
    for(int i = 0;i<=n;i++) f[i][0] = i;
    for(int i = 0;i<=m;i++) f[0][i] = i;
    for(int i = 1;i<=n;i++){
        for(int j = 1;j<=m;j++){
            f[i][j] = min(f[i][j-1],f[i-1][j]) + 1;
            if(word1[i - 1] == word2[j-1])
                f[i][j] = min(f[i][j],f[i-1][j-1]);
        }
    }
    return f[n][m];
}
int min(int x,int y){
    if(x > y) return y;
    else return x;
}

Go：

func minDistance(word1 string, word2 string) int {
    n := len(word1)
    m := len(word2)
    var f = [510][510]int {}
    for i:=0;i<=m;i++ {
        f[0][i] = i
    }
    for i:=0;i<=n;i++ {
        f[i][0] = i
    }
    for i:=1;i<=n;i++ {
        for j:=1;j<=m;j++ {
            f[i][j] = Min(f[i-1][j],f[i][j-1]) + 1
            if word1[i - 1] == word2[j - 1] {
                f[i][j] = Min(f[i][j],f[i-1][j-1])
            }
        }
    }
    return f[n][m]
}
func Min(x int,y int) int{
    if x < y {
        return x
    } else {
        return y
    }
}

Python3：

	def minDistance(self, word1: str, word2: str) -> int:
        n = len(word1)
        m = len(word2)
        f = [[0]*510 for i in range(510)]
        for i in range(0,n + 1):
            f[i][0] = i
        for i in range(0,m + 1):
            f[0][i] = i
        for i in range(1,n+1):
            for j in range(1,m+1):
                f[i][j] = min(f[i - 1][j],f[i][j - 1]) + 1
                if word1[i - 1] == word2[j - 1]:
                    f[i][j] = min(f[i][j],f[i - 1][j - 1])
                else:
                    f[i][j] = min(f[i][j],f[i - 1][j - 1] + 1)
        return f[n][m]

编程语言：

C/C++/Go/Python

完整代码：

c++：

    int f[110][110];
    int minDistance(string word1, string word2) {
        int n = word1.size();
        int m = word2.size();
        for(int i =0;i<=n;i++) f[i][0] = i;
        for(int i =0;i<=m;i++) f[0][i] = i;
        for(int i = 1;i<=n;i++){
            for(int j = 1;j<=m;j++){
                f[i][j] = min(f[i][j - 1],f[i-1][j]) + 1;
                if(word1[i-1] == word2[j-1]) f[i][j] = min(f[i][j],f[i-1][j-1]);
            }
        }
        return f[n][m];
    }

C：

int f[510][510];
int minDistance(char * word1, char * word2){
    int n = strlen(word1);
    int m = strlen(word2);
    for(int i = 0;i<=n;i++) f[i][0] = i;
    for(int i = 0;i<=m;i++) f[0][i] = i;
    for(int i = 1;i<=n;i++){
        for(int j = 1;j<=m;j++){
            f[i][j] = min(f[i][j-1],f[i-1][j]) + 1;
            if(word1[i - 1] == word2[j-1])
                f[i][j] = min(f[i][j],f[i-1][j-1]);
        }
    }
    return f[n][m];
}
int min(int x,int y){
    if(x > y) return y;
    else return x;
}

Go：

func minDistance(word1 string, word2 string) int {
    n := len(word1)
    m := len(word2)
    var f = [510][510]int {}
    for i:=0;i<=m;i++ {
        f[0][i] = i
    }
    for i:=0;i<=n;i++ {
        f[i][0] = i
    }
    for i:=1;i<=n;i++ {
        for j:=1;j<=m;j++ {
            f[i][j] = Min(f[i-1][j],f[i][j-1]) + 1
            if word1[i - 1] == word2[j - 1] {
                f[i][j] = Min(f[i][j],f[i-1][j-1])
            }
        }
    }
    return f[n][m]
}
func Min(x int,y int) int{
    if x < y {
        return x
    } else {
        return y
    }
}

Python3：

	def minDistance(self, word1: str, word2: str) -> int:
        n = len(word1)
        m = len(word2)
        f = [[0]*510 for i in range(510)]
        for i in range(0,n + 1):
            f[i][0] = i
        for i in range(0,m + 1):
            f[0][i] = i
        for i in range(1,n+1):
            for j in range(1,m+1):
                f[i][j] = min(f[i - 1][j],f[i][j - 1]) + 1
                if word1[i - 1] == word2[j - 1]:
                    f[i][j] = min(f[i][j],f[i - 1][j - 1])
                else:
                    f[i][j] = min(f[i][j],f[i - 1][j - 1] + 1)
        return f[n][m]