Chương trình tìm giá trị K cho chuỗi K-tương tự trong C++

Mô tả bài toán

Hai chuỗi s và t là K-tương tự nếu hoán vị hai ký tự trong s đúng K lần cho ra t. Cho hai anagram s và t, tìm K nhỏ nhất.

Ví dụ

s = "abc", t = "bac" -> 1.

Giải thuật (BFS trên trạng thái chuỗi)

1. Nếu A == B trả về 0.
2. BFS từ A, mỗi trạng thái là một chuỗi.
3. Tìm vị trí i đầu tiên khác nhau giữa trạng thái hiện tại và B.
4. Thử hoán vị i với j > i nếu curr[j] == B[i] và curr[j] != B[j].
5. Nếu trạng thái mới == B -> trả về level hiện tại.
6. Dùng tập visited tránh lặp.

Triển khai C++

#include 
using namespace std;

class Solution {
public:
    int kSimilarity(string A, string B) {
        if (A == B) return 0;
        unordered_set visited;
        visited.insert(A);
        queue 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;
                    swapp(curr, i, j);
                    if (curr == B) return lvl;
                    if (!visited.count(curr)) {
                        visited.insert(curr);
                        q.push(curr);
                    }
                    swapp(curr, i, j);
                }
            }
        }
        return -1;
    }
    void swapp(string &s, int i, int j) {
        char x = s[i], y = s[j];
        s[i] = y; s[j] = x;
    }
};

int main() {
    Solution ob;
    cout << ob.kSimilarity("abc", "bac");
}

Đầu vào

"abc", "bac"

Đầu ra

1