โปรแกรมหาค่า K สำหรับ K-Similar Strings ใน C++

สองสตริง s, t เรียกว่า K-similar ถ้าสลับตัวอักษรใน s ทั้งหมด K ครั้ง ได้ t หา K น้อยที่สุด (s, t เป็น anagram กัน)

ตัวอย่าง: s="abc", t="bac" ผลลัพธ์ 1

วิธีแก้ปัญหา (BFS)

1. ถ้า A==B คืน 0
2. BFS จาก A ระดับ lvl:
   • ดึงสตริง curr หา i แรกที่ curr[i]!=B[i]
   • ลองสลับ curr[i] กับ curr[j] (j>i) ที่ curr[j]==B[i] และ curr[j]!=B[j]
   • ถ้าได้ B คืน lvl
   • เก็บ visited ป้องกันซ้ำ

ตัวอย่างโค้ด (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;
                    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"); }

อินพุต

"abc", "bac"

เอาต์พุต

1