题解 | #编辑距离(一)#

动态规划， 二维数组 comp[i][j] 项表示当str1的前i个字符匹配str2的前j个字符需要做的变化量。然后分两种情况，str1[i],str2[j]相同和不同，代码里应该很清楚了

class Solution {
public:
/**
 * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
 *
 * 
 * @param str1 string字符串 
 * @param str2 string字符串 
 * @return int整型
 */
int editDistance(string str1, string str2) {
    int s1 = str1.size() + 1;
    int s2 = str2.size() + 1;
    vector<vector<int>> comp(s1, vector<int>(s2));
    comp[0][0] = 0;
    for (int i = 1; i < s2; i ++) {
        comp[0][i] = i;
    }
    
    for (int i = 1; i < s1; i ++) {
        comp[i][0] = i;
    }
    for (int i = 1; i <s1; i++) {
        for(int j = 1; j < s2; j++) {
            if (str1[i - 1] == str2[j - 1]) {
                comp[i][j] = comp[i-1][j-1];
            } else {
            	// 分别采用增，删，改，三种方式变成相同，选出成最小的。
                comp[i][j] = min(min(comp[i-1][j], comp[i][j-1]),comp[i-1][j - 1]) + 1;
            }
            
        }
    }
    return comp[s1-1][s2-1];
}
};