두 개의 문자열 s와 t가 있다고 가정합니다. 결과 문자열이 t가 되도록 s에 있는 두 문자의 위치를 정확히 K번 교환할 수 있다면 이 두 문자열은 K 유사합니다. 따라서 우리는 s와 t 두 개의 아나그램을 가지고 있으며 s와 t가 K-유사한 가장 작은 K를 찾아야 합니다.
따라서 입력이 s ="abc" t ="bac"와 같으면 출력은 1이 됩니다.
이 문제를 해결하기 위해 다음 단계를 따릅니다. −
-
이웃() 함수를 정의합니다. new_data
가 필요합니다. -
new_data의 각 인덱스 i와 값 c에 대해
-
c가 t[i]와 같지 않으면
-
루프에서 나오다
-
-
-
범위 i+1에서 new_data - 1의 크기에 있는 j에 대해 수행
-
u[j]가 t[i]와 같으면
-
교환 new_data[i] new_data[j]
-
new_data의 모든 요소를 결합하여 문자열을 생성하고 다음 호출에서 반환, 이 영역에서 다시 시작
-
교환 new_data[i] new_data[j]
-
-
-
기본 방법에서 다음을 수행합니다.
-
q :=하나의 큐를 삽입 쌍(s, 0)으로 만들기
-
본 :=s의 새 세트
-
q가 비어 있지 않은 동안 수행
-
(u, swap_cnt) :=q의 첫 번째 항목 및 q에서 삭제
-
u가 t와 같으면
-
swap_cnt 반환
-
-
이웃의 각 v에 대해(u를 목록으로) 수행
-
v가 보이지 않으면
-
v를 본 대로 표시
-
q의 끝에 (v, swap_cnt+1) 삽입
-
-
-
-
0 반환
예
더 나은 이해를 위해 다음 구현을 살펴보겠습니다.
from collections import deque
def solve(s, t):
def swap(data, i, j):
data[i], data[j] = data[j], data[i]
def neighbors(new_data):
for i, c in enumerate(new_data):
if c != t[i]: break
for j in range(i+1, len(new_data)):
if u[j] == t[i]:
swap(new_data, i, j)
yield "".join(new_data)
swap(new_data, i, j)
q = deque([(s, 0)])
seen = set(s)
while q:
u, swap_cnt = q.popleft()
if u == t:
return swap_cnt
for v in neighbors(list(u)):
if v not in seen:
seen.add(v)
q.append((v, swap_cnt+1))
return 0
s = "abc"
t = "bac"
print(solve(s, t)) 입력
"abc, bac"
출력
1