두 개의 문자열 A와 B가 있다고 가정합니다. 결과 문자열이 B가 되도록 A에서 두 문자의 위치를 정확히 K번 교환할 수 있다면 이 두 문자열은 K 유사합니다(여기서 K는 음이 아닌 정수 하나). 두 개의 아나그램 A와 B, 우리는 A와 B가 K-유사한 가장 작은 K를 찾아야 합니다.
따라서 입력이 A ="abc", B ="bac"와 같으면 출력은 2가 됩니다.
이 문제를 해결하기 위해 다음 단계를 따릅니다. −
-
함수 swapp()를 정의하면 문자열 s, i, j,
가 사용됩니다. -
x :=s[i], y :=s[j]
-
s[i] :=y, s[j] :=x
-
주요 방법에서 다음을 수행하십시오 -
-
A가 B와 같으면 0을 반환합니다.
-
방문한 한 세트 정의
-
방문에 A 삽입
-
하나의 대기열 q를 정의하고 A를 q에 삽입
-
initialize lvl :=1의 경우 q가 비어 있지 않으면 업데이트(lvl을 1만큼 증가)하고 -
를 수행합니다.-
sz :=q의 크기
-
sz가 0이 아닌 동안 각 반복에서 sz를 1씩 줄입니다. -
-
curr :=q의 첫 번째 요소
-
q에서 요소 삭제
-
나는 :=0
-
동안 (i
-
(i를 1씩 증가)
-
-
j 초기화의 경우:=i + 1, j
-
curr[i]가 curr[j]와 같으면 -
-
다음 부분은 무시하고 다음 반복으로 건너뜁니다.
-
-
curr[j]가 B[i]와 같지 않으면 -
-
다음 부분은 무시하고 다음 반복으로 건너뜁니다.
-
-
curr[j]가 B[j]와 같으면 -
-
다음 부분은 무시하고 다음 반복으로 건너뜁니다.
-
-
스왑(curr, i, j)
-
curr이 B와 같으면 -
-
레벨을 반환
-
-
방문 횟수(curr)가 아닌 경우 -
-
방문에 curr 삽입
-
q에 curr 삽입
-
-
스왑(curr, i, j)
-
-
-
-
반환 -1
이해를 돕기 위해 다음 구현을 살펴보겠습니다. −
예시
#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"));
} 입력
"abc", "bac"
출력
1