Untitled
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