//
// Created by Ruizhe Hou on 2020/9/26.
//
#include <iostream>
#include <vector>
#include <string>

using namespace std;

class Solution {
public:
    /**
     * @param words: a set of stirngs
     * @param target: a target string
     * @param k: An integer
     * @return: output all the strings that meet the requirements
     */

    int minDistance(string word1, string word2, int k) {
        int m = word1.size();
        int n = word2.size();
        if (m - n > k || n - m > k) return k + 1;
        vector<vector<int>> dp(m + 1, vector<int>(n + 1));
        for (int i = 0; i <= m; i++) {
            dp[i][0] = i;
        }
        for (int j = 0; j <= n; j++) {
            dp[0][j] = j;
        }
        for (int i = 1; i <= m; i++) {
            for (int j = 1; j <= n; j++) {
                if (word1[i - 1] == word2[j - 1])
                    dp[i][j] = dp[i - 1][j - 1];
                else {
                    dp[i][j] = 1 + min(dp[i - 1][j - 1], min(dp[i][j - 1], dp[i - 1][j]));
                }
            }
        }
        return dp[m][n];
    }

    vector<string> kDistance(vector<string> &words, string &target, int k) {
        // write your code here
        vector<string> res;
        for (auto &word: words) {
            if (minDistance(word, target, k) <= k) {
                res.push_back(word);
            }
        }
        return res;
    }
};

int main() {
    Solution sol;
    vector<string> words = {"abc", "abd", "abcd", "adc"};
    string target = "abc";
    auto res = sol.kDistance(words, target, 1);
    for (auto &w : res) cout << w << " ";
    cout << endl;
    return 0;
}