C++를 사용하여 두 문자열을 동일하게 만드는 데 필요한 주어진 작업의 최소 수입니다.

문제 설명

두 개의 문자열 str1과 str2가 주어지면 두 문자열 모두 'a'와 'b' 문자를 포함합니다. 두 문자열의 길이는 동일합니다. 두 문자열 모두에 하나의 _(빈 공간)가 있습니다. 작업은 다음 작업의 최소 수를 수행하여 첫 번째 문자열을 두 번째 문자열로 변환하는 것입니다 -

• _가 위치 I에 있으면 _는 위치 i+1 또는 i-1에 있는 문자로 교체될 수 있습니다.

• 위치 i+1 및 i+2의 문자가 다른 경우 _는 위치 i+1 또는 i+2의 문자로 교체될 수 있습니다.

• 유사하게, 위치 i-1과 i-2의 문자가 다른 경우 _는 위치 i-1 또는 i-2의 문자로 교체될 수 있습니다.

str1 ="aba_a"이고 str2 ="_baaa"이면 str1을 str2로 변환하기 위해 2번의 이동이 필요합니다 -

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

알고리즘

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.

예시

#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;
}

출력

위의 프로그램을 컴파일하고 실행할 때. 다음 출력을 생성합니다 -

Minimum required moves: 2