LeetCode 72. Edit Distance调试模板-wowAC

此代码为了方便大家调试用,使用的时候直接用自己的Solution类覆盖代码中的类,程序的输入文件路径默认在桌面的data_in.txt,使用的时候直接将LeetCode的case复制进文件即可。如下图所示。

image.png


#include <iostream>
#include <fstream>

using namespace std;

/***************改成自己的代码****************/
class Solution {
public:
    int minDistance(string word1, string word2) {
        int dp[500][500];
        dp[0][0] = 0;
        //边界条件
        for(int i=1; i<=word1.size(); i++) dp[i][0] = i;
        for(int j=1; j<=word2.size(); j++) dp[0][j] = j;

        for(int i=1; i<=word1.size(); i++)
        for(int j=1; j<=word2.size(); j++) {
            int res = 0x3f3f3f3f;
            res = min(res, dp[i-1][j]+1);   //删除i
            res = min(res, dp[i][j-1]+1);   //增加word2[j]
            if(word1[i-1] == word2[j-1])
                res = min(res, dp[i-1][j-1]); //都一样不需要操作
            else
                res = min(res, dp[i-1][j-1]+1); //将word1[i-1]改为word2[j-1]
            dp[i][j] = res;
        }
        return dp[word1.size()][word2.size()];
    }
};
/***************到此为止****************/

int main()
{
    //改成自己的输入路径,注意用双斜杠分割 默认输入文件为桌面的data_in.txt
    fstream fin("C:\\Users\\xingxing\\Desktop\\data_in.txt");
    string word1, word2;
    Solution solu;
    int kase = 1;
    while(getline(fin, word1)) {
        if(line == "") continue;
        getline(fin, word2);
        word1 = word1.substr(1, word1.length()-2);
        word2 = word2.substr(1, word2.length()-2);

        cout<<"case"<<kase++<<": "<<endl;
        cout<<solu.minDistance(word1, word2)<<endl;
    }
    return 0;
}

发表评论

电子邮件地址不会被公开。 必填项已用*标注