Yêu cầu số lượng tối thiểu các hoạt động nhất định để tạo hai chuỗi bằng nhau bằng cách sử dụng C ++.

Tuyên bố vấn đề

Cho hai chuỗi str1 và str2, cả hai chuỗi đều chứa các ký tự ‘a’ và ‘b’. Cả hai chuỗi có độ dài bằng nhau. Có một _ (không gian trống) trong cả hai chuỗi. Nhiệm vụ là chuyển đổi chuỗi đầu tiên thành chuỗi thứ hai bằng cách thực hiện số lượng tối thiểu các phép toán sau -

• Nếu _ ở vị trí I thì _ có thể được hoán đổi bằng một ký tự ở vị trí i + 1 hoặc i-1

• Nếu các ký tự ở vị trí i + 1 và i + 2 khác nhau thì _ có thể được hoán đổi bằng một ký tự ở vị trí i + 1 hoặc i + 2

• Tương tự, nếu các ký tự ở vị trí i-1 và i-2 khác nhau thì _ có thể được hoán đổi bằng một ký tự ở vị trí i-1 hoặc i-2

Nếu str1 =“aba_a” và str2 =“_baaa” thì chúng ta cần 2 lần di chuyển để biến đổi str1 thành str2 -

1. str1 = “ab_aa” (Swapped str1[2] with str1[3])
2. str2 = “_baaa” (Swapped str1[0] with str1[2])

Thuật toán

1. Apply a simple Breadth First Search over the string and an element of the queue used for BFS will contain the pair str, pos where pos is the position of _ in the string str.
2. Also maintain a map namely ‘vis’ which will store the string as key and the minimum moves to get to the string as value.
3. For every string str from the queue, generate a new string tmp based on the four conditions given and update the vis map as vis[tmp] = vis[str] + 1.
4. Repeat the above steps until the queue is empty or the required string is generated i.e. tmp == B
5. If the required string is generated, then return vis[str] + 1 which is the minimum number of operations required to change A to B.

Ví dụ

#include <iostream>
#include <string>
#include <unordered_map>
#include <queue>
using namespace std;
int transformString(string str, string f){
   unordered_map<string, int> vis;
   int n;
   n = str.length();
   int pos = 0;
   for (int i = 0; i < str.length(); i++) {
      if (str[i] == '_') {
         pos = i;
         break;
      }
   }
   queue<pair<string, int> > q;
   q.push({ str, pos });
   vis[str] = 0;
   while (!q.empty()) {
      string ss = q.front().first;
      int pp = q.front().second;
      int dist = vis[ss];
      q.pop();
      if (pp > 0) {
         swap(ss[pp], ss[pp - 1]);
         if (!vis.count(ss)) {
            if (ss == f) {
               return dist + 1;
               break;
            }
            vis[ss] = dist + 1;
            q.push({ ss, pp - 1 });
         }
         swap(ss[pp], ss[pp - 1]);
      }
      if (pp < n - 1) {
         swap(ss[pp], ss[pp + 1]);
         if (!vis.count(ss)) {
         if (ss == f) {
            return dist + 1;
            break;
         }
         vis[ss] = dist + 1;
         q.push({ ss, pp + 1 });
      }
      swap(ss[pp], ss[pp + 1]);
   }
   if (pp > 1 && ss[pp - 1] != ss[pp - 2]) {
      swap(ss[pp], ss[pp - 2]);
      if (!vis.count(ss)) {
         if (ss == f) {
            return dist + 1;
            break;
         }
         vis[ss] = dist + 1;
         q.push({ ss, pp - 2 });
      }
      swap(ss[pp], ss[pp - 2]);
   }
   if (pp < n - 2 && ss[pp + 1] != ss[pp + 2]) {
      swap(ss[pp], ss[pp + 2]);
      if (!vis.count(ss)) {
         if (ss == f) {
            return dist + 1;
            break;
         }
         vis[ss] = dist + 1;
         q.push({ ss, pp + 2 });
      }
      swap(ss[pp], ss[pp + 2]);
      }
   }
   return 0;
}
int main(){
   string str1 = "aba_a";
   string str2 = "_baaa";
   cout << "Minimum required moves: " << transformString(str1, str2) << endl;
   return 0;
}

Đầu ra

Khi bạn biên dịch và thực thi chương trình trên. Nó tạo ra kết quả sau -

Minimum required moves: 2