Contents

1. 1. 1. 什么是字符串编辑距离
2. 2. 2. 字符串的最小编辑距离即要求 给定两个字符串A和B，使得用最小的编辑距离达到 A=B
3. 3. 3. 求解两个字符串A和B的最小编辑距离，利用动态规划的思想。

1. 什么是字符串编辑距离

• 编辑距离（Edit Distance），又称Levenshtein距离，是指两个字串之间，由一个转成另一个所需的最少编辑操作次数。许可的编辑操作包括将一个字符替换成另一个字符，添加一个字符，删除一个字符。
• 例如将kitten一字转成sitting：
  a. sitten （k→s）
  b. sittin （e→i）
  c. sitting （→g）
  俄罗斯科学家Vladimir Levenshtein在1965年提出这个概念。

2. 字符串的最小编辑距离即要求 给定两个字符串A和B，使得用最小的编辑距离达到 A=B

3. 求解两个字符串A和B的最小编辑距离，利用动态规划的思想。

• 假设状态dp[i][j] 表示的是字符串A的子串 A[0-i]和字符串B的子串B[0-j]的最小编辑距离，那么有如下几个结论
  i = 0，j = 0，dp[0][0] = 0，两个空串最小编辑距离为0
  i = 0，j > 0，dp[i][j] = j，字符串A的子串为空则编辑距离为字符串B的子串长度 j
  i > 0，j = 0，dp[i][j] = i，字符串B的子串为空则编辑距离为字符串A的子串长度 i
  i > 0，j > 0，A[i] = B[j]，dp[i][j] = dp[i-1][j-1]，字符串A的子串最后一个字符等于字符串B子串的最后一个字符
  i > 0，j > 0，A[I] != B[j]，dp[i][j] = min{dp[i-1][j] + 1, dp[i][j-1] + 1, dp[i-1][j-1] + 1}，dp[i-1][j] + 1表示的是字符串A的子串添加一个字符，dp[i][j-1]表示的是字符串B的子串添加一个字符，dp[i-1][j-1] + 1表示字符串A的子串替换一个字符。

#include <cstdio>
#include <string>
#include <iostream>
#include <algorithm>
using namespace std;

#define MAX 50
#define INT_MAX 0x7ffffff

// get min edit dis
int GetEditDis(const string& strOne, const string& strTwo) {
    int dp[MAX][MAX];
    int strOneLength = strOne.length();
    int strTwoLength = strTwo.length();

    for (int i = 0; i <= strOneLength; ++i) {
        dp[i][0] = i; // strTwo subStr is empty
    }
    for (int j = 0; j <= strTwoLength; ++j) {
        dp[0][j] = j; // strOne subStr is empty
    }

    for (int i = 0; i < strOneLength; ++i) {
        for (int j = 0; j < strTwoLength; ++j) {
            int strOneAdd, strTwoAdd, rep;
            strOneAdd = dp[i][j+1] + 1; // strOne add char
            strTwoAdd = dp[i+1][j] + 1; // strTwo add char
            strOne[i] == strTwo[j] ? rep = 0 : rep = 1;
            dp[i+1][j+1] = min(min(strOneAdd, strTwoAdd), dp[i][j]+rep);
        }
    }
    return dp[strOneLength][strTwoLength];
}

int main(int argc, char **argv) {
    string strOne = "kitten";
    string strTwo = "sitting";

    cout << GetEditDis(strOne, strTwo) << endl; // cout 3

    return 0;
}