//
// Created by 罗炳国 on 2023/7/16.
//

#ifndef PFJ_CODE05_MINDISTANCE_H
#define PFJ_CODE05_MINDISTANCE_H

#include "commonHeader.h"

/*
    给你两个单词word1 和word2， 请返回将word1转换成word2 所使用的最少操作数 。
你可以对一个单词进行如下三种操作：

插入一个字符
删除一个字符
替换一个字符

来源：力扣（LeetCode）
链接：https://leetcode.cn/problems/edit-distance
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
 * */

class code05_minDistance {
public:
    int minDistance(string s1, string s2) {
        int N = s1.size() + 1;
        int M = s2.size() + 1;

        if (N == 0) return M;
        if (M == 0) return N;

        vector<int> dp(M * N, 0);

        for (int i = 0; i < N; i++) {
            dp[i * M] = i;// 删除
        }
        for (int j = 0; j < M; j ++) {
            dp[j] = j;
        }

        for (int i = 1; i < N; i++) {
            for (int j = 1; j < M; j++) {
                dp[i * M + j] = dp[(i - 1) * M + (j - 1)] + (s1[i - 1] == s2[j - 1] ? 0 : 1);
                dp[i * M + j] = min(dp[i * M + j], dp[i * M + j - 1] + 1);
                dp[i * M + j] = min(dp[i * M + j], dp[(i - 1) * M + j] + 1);
            }
        }
        std::cout << M * N << endl;
        for (int i = 0; i < M * N; i++)
            std::cout << dp[i] << " ";
        std::cout << endl;
        return dp[N * M - 1];
    }

    void test() {
        string s1("horse");
        string s2("ros");
        int ans = minDistance(s1, s2);
        std::cout << ans << std::endl;
    }
};

#endif //PFJ_CODE05_MINDISTANCE_H