[LeetCode] [动态规划] [编辑距离] Edit Distance

Given two words word1 and word2, find the minimum number of steps required to convertword1 toword2. (each operation is counted as 1 step.)

You have the following 3 operations permitted on a word:

c) Replace a character

问题描述：给定两个单词word1和word2，找到将word1转换成word2的最小步数，每个操作计作一步，有增加、删除、替换三个操作。

编辑距离问题是动态规划的典型问题，只不过这里将编辑距离的代价换成了操作步数。

设m = word1.size()，n = word2.size()，二维数组distance[m + 1][n + 1]保存转换的最小步数，distance[i][j]保存的是长度为i的串转换成长度为j的串的最小步数。

那么有：

distance[0][0] = 0;

distance[j][0] = j;

distance[0][i] = i;

并且distance[j][i] = min(distance[j][i - 1] + insert, distance[j - 1][i] + delete, distance[j - 1][i - 1] + replace);

注意，这里的replace的步数要根据word1[j]与word2[i]的关系来得到，但是由于这里的索引是以1开始，而字符串的索引以0开始，因此，要判断word1[j - 1]与word2[i - 1]的关系：

当word1[j - 1] == word1[i - 1]时，replace = 0，否则replace = 2。

class Solution {
    const int insert_cost = 1;
    const int delete_cost = 1;
    
    int substitute_cost(char x, char y)
    {
	    if(x == y)
	        return 0;
	    else
	        return 1;
    }

    int min3(int x, int y, int z)
    {
	    return min(min(x, y), z);
    }
public:
    int minDistance(string word1, string word2) {
        int source_len = word1.size();
	    int target_len = word2.size();
	    vector
  
    > vec;
	    vector
   
     ivec; int i = 0, j = 0; for(i = 0; i <= target_len; ++i) { ivec.push_back(i); } vec.push_back(ivec); for(i = 1; i <= source_len; ++i) { ivec.clear(); ivec.push_back(i); for(j = 0; j < target_len; ++j) { ivec.push_back(0); } vec.push_back(ivec); } for(i = 1; i <= target_len; ++i) { for(j = 1; j <= source_len; ++j) { vec[j][i] = min3(vec[j][i - 1] + insert_cost, \ vec[j - 1][i] + delete_cost, \ vec[j - 1][i - 1] + substitute_cost(word1[j - 1], word2[i - 1])); } } return vec[source_len][target_len]; } };