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

class Solution {
public:
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     * 
     * @param str1 string字符串 
     * @param str2 string字符串 
     * @return int整型
     */
    int editDistance(string str1, string str2) {
        // write code here
        // 计算通过插入、删除、修改一个字符需要的步骤
        // 类似计算最长公共子序列，如果子序列之间距离不一致使用插入、删除。一致则使用修改，
        // 记录编辑距离，当两个值相等，编辑距离不变，否则加值修改
        int Asize = str1.size();
        int Bsize = str2.size();
        vector<vector<int>> value2(Asize+1, vector(Bsize+1, 0)); // 记录编辑距离
         // 需要注意的是，需要注意i=0.j=0的情况, 默认赋值为index
        for(int i = 0; i<=Asize; i++){
            value2[i][0] = i;
        }
        for(int j = 0; j<=Bsize; j++){
            value2[0][j] = j;
        }
       
        for(int i = 1; i<=Asize; i++){
            for(int j = 1; j<=Bsize; j++){
                // 如果相等
                
                if(str1[i-1] == str2[j-1]){
                    cout<<i-1<<","<<j-1<<","<<str1[i-1]<<","<<str2[j-1]<<endl;
                    value2[i][j] = value2[i-1][j-1];
                }
                else{
                    // 取插入，删除，修改的值的最小值
                    int a = value2[i-1][j];
                    int b = value2[i][j-1];
                    int c = value2[i-1][j-1];
                    value2[i][j] = min(a,min(b,c))+1; //只要不相等就需要+1
                    
                }
            }
        }
        cout<<"XXXXX"<<endl;
        for(int i = 0; i<Asize; i++){
            for(int j = 0; j<Bsize; j++){
                cout<<value2[i][j];
            }
            cout<<endl;
        }
        cout<<"XXXXX"<<endl;
        
        return value2[Asize][Bsize];
    }
};