Untitled

 avatar
unknown
c_cpp
9 days ago
1.2 kB
6
Indexable
int solve(const string& a, const string& b) {
    int m = a.length();
    int n = b.length();
    vector<vector<int>> dp(m + 1, vector<int>(n + 1, 0));

    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 (a[i - 1] == b[j - 1])
                dp[i][j] = dp[i - 1][j - 1];
            else
                dp[i][j] = 1 + min({ dp[i - 1][j], dp[i][j - 1], dp[i - 1][j - 1] });

    return dp[m][n];
}

vector<string> MinimumContrast(int n, vector<string> S, int q, vector<string> Q) {
    vector<string> result;

    for (int i = 0; i < q; ++i) {
        string query = Q[i];
        int minDist = INT_MAX;
        string closest = "";

        for (int j = 0; j < n; ++j) {
            int dist = solve(query, S[j]);
            if (dist < minDist) {
                minDist = dist;
                closest = S[j];
            }
            else if (dist == minDist && closest.empty()) {
                closest = S[j];
            }
        }

        result.push_back(closest);
    }

    return result;
}
Editor is loading...
Leave a Comment