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

Giả sử chúng ta có hai chuỗi s và t. Hai chuỗi này giống nhau K khi chúng ta có thể hoán đổi vị trí của hai chữ cái trong s đúng K lần để chuỗi kết quả là t. Chúng ta có hai chữ cái đảo chữ s và t, và chúng ta phải tìm K nhỏ nhất mà s và t tương tự K.

Vì vậy, nếu đầu vào là s =​​"abc", t ="bac", thì đầu ra sẽ là 1.

Để giải quyết vấn đề này, chúng tôi sẽ làm theo các bước sau -

• Xác định một hàm swapp (), điều này sẽ lấy chuỗi s, i, j,

• x:=s [i], y:=s [j]

• s [i]:=y, s [j]:=x

• Từ phương thức chính, hãy làm như sau -

• nếu A giống B, thì :, trả về 0

• Xác định một tập hợp đã truy cập

• chèn A vào đã truy cập

• Xác định một hàng đợi q, chèn A vào q

• để khởi tạo lvl:=1, khi không phải q trống, hãy cập nhật (tăng lvl lên 1), thực hiện -

  • sz:=kích thước của q

  • trong khi sz khác 0, giảm sz đi 1 trong mỗi lần lặp, thực hiện:

    • curr:=phần tử đầu tiên của q

    • xóa phần tử khỏi q

    • i:=0

    • while (i

      • (tăng tôi lên 1)

    • để khởi tạo j:=i + 1, khi j

      • nếu curr [i] giống với curr [j], thì:

        • Bỏ qua phần sau, chuyển sang phần tiếp theo

      • nếu curr [j] không bằng B [i] thì:

        • Bỏ qua phần sau, chuyển sang phần tiếp theo

      • nếu curr [j] giống với B [j] thì:

        • Bỏ qua phần sau, chuyển sang phần tiếp theo

      • swapp (curr, i, j)

      • nếu curr giống với B, thì:

        • trả về lvl

      • nếu không phải là số lượng cuộc gọi (curr) đã truy cập, thì:

        • chèn curr vào đã ghé thăm

        • chèn curr vào q

      • swapp (curr, i, j)

• trả về -1

Ví dụ

Hãy cùng chúng tôi xem cách triển khai sau đây để hiểu rõ hơn

#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;
               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];
      char y = s[j];
      s[i] = y;
      s[j] = x;
   }
};

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

Đầu vào

"abc", "bac"

Đầu ra

1