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

Giả sử chúng ta có hai chuỗi A và B. Hai chuỗi này giống nhau K (với K là một số nguyên không âm) nếu chúng ta có thể hoán đổi vị trí của hai chữ cái trong A đúng K lần để chuỗi kết quả là B. Vì vậy, chúng ta có hai phép đảo chữ A và B, chúng ta phải tìm K nhỏ nhất mà A và B tương tự K.

Vì vậy, nếu đầu vào là A ="abc", B ="bac", thì đầu ra sẽ là 2.

Để 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, thực hiện 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

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

Ví dụ

#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"

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

Ví dụ

Đầu vào

Đầu ra