Chuỗi K-tương đồng trong C++

Hai chuỗi A, B là K-tương đồng nếu hoán vị 2 ký tự trong A đúng K lần được B. Cho A, B là anagram, tìm K nhỏ nhất.

Ví dụ: A="abc", B="bac" → 1 (hoán vị a và b).

Giải thuật

1. BFS từ A, mỗi trạng thái là một chuỗi. Mức lvl = số lần hoán vị.
2. Tìm vị trí i đầu tiên mà curr[i] != B[i].
3. Thử hoán vị curr[i] với curr[j] (j > i) sao cho: curr[j] == B[i] VÀ curr[j] != B[j] VÀ curr[i] != curr[j] (cắt tỉa).
4. Nếu sau hoán vị curr == B → trả về lvl.
5. Dùng set visited tránh lặp.

Ví dụ mã C++

#include <bits/stdc++.h>
using namespace std;
class Solution {
public:
    int kSimilarity(string A, string B) {
        if (A == B) return 0;
        unordered_set<string> visited;
        visited.insert(A);
        queue<string> q;
        q.push(A);
        for (int lvl = 1; !q.empty(); lvl++) {
            int sz = q.size();
            while (sz--) {
                string curr = q.front(); q.pop();
                int i = 0;
                while (i < curr.size() && curr[i] == B[i]) i++;
                for (int j = i + 1; j < curr.size(); j++) {
                    if (curr[i] == curr[j]) continue;
                    if (curr[j] != B[i]) continue;
                    if (curr[j] == B[j]) continue;
                    swap(curr[i], curr[j]);
                    if (curr == B) return lvl;
                    if (!visited.count(curr)) { visited.insert(curr); q.push(curr); }
                    swap(curr[i], curr[j]);
                }
            }
        }
        return -1;
    }
};
int main(){
    Solution ob;
    cout << (ob.kSimilarity("abc", "bac"));
}

Đầu vào

"abc", "bac"

Đầu ra

1