파이썬에서 주어진 아나그램을 만드는 데 필요한 최소 스왑을 찾는 프로그램

<시간/>

두 개의 문자열 S와 T가 있고 서로의 아나그램이라고 가정합니다. T와 같게 하려면 S에 필요한 최소 스왑 수를 찾아야 합니다.

따라서 입력이 S ="kolkata" T ="katloka"와 같은 경우 출력은 3이 됩니다. 이 순서로 [katloka(주어진), kotlaka, koltaka, kolkata]를 바꿀 수 있습니다.

이 문제를 해결하기 위해 다음 단계를 따릅니다. −

util() 함수를 정의합니다. S, T, i가 필요합니다.
i>=S의 크기이면
- 0을 반환
S[i]가 T[i]와 같으면
- return util(S, T, i + 1)
x :=T[i]
ret :=99999
i + 1 범위에서 T 크기까지의 j에 대해 다음을 수행합니다.
- x가 S[j]와 같으면
  - S[i]와 S[j] 교환
  - ret :=ret의 최소값 및 (1 + util(S, T, i + 1))
  - S[i]와 S[j] 교환
반환
기본 방법에서 다음을 수행합니다.
return util(S, T, 0)

이해를 돕기 위해 다음 구현을 살펴보겠습니다. −

예시

class Solution:
   def util(self, S, T, i) :
      S = list(S)
      T = list(T)
      if i >= len(S):
         return 0
      if S[i] == T[i]:
         return self.util(S, T, i + 1)
      x = T[i]
      ret = 99999;
      for j in range(i + 1, len(T)):
         if x == S[j]:
            S[i], S[j] = S[j], S[i]
            ret = min(ret, 1 + self.util(S, T, i + 1))
            S[i], S[j] = S[j], S[i]
      return ret
     
   def solve(self, S, T):
      return self.util(S, T, 0)

ob = Solution()
S = "kolkata"
T = "katloka"
print(ob.solve(S, T))

입력

"kolkata", "katloka"