문자열 s가 있다고 가정하고 회문으로 만드는 데 필요한 최소 인접 스왑 수를 찾아야 합니다. 해결 방법이 없으면 -1을 반환합니다.
따라서 입력이 s ="xxyy"와 같으면 출력은 2가 됩니다. 가운데 "x"와 "y"를 교환하여 문자열이 "xyxy"가 되도록 한 다음 처음 두 "x"와 " y"는 "yxxy"를 가져오고 이것은 회문입니다.
이 문제를 해결하기 위해 다음 단계를 따릅니다. −
-
util() 함수를 정의합니다. 시간이 걸립니다
-
본 :=새 지도
-
s의 각 i에 대해 수행
-
본[i] :=1 + (존재하는 경우 본[i] 그렇지 않으면 0)
-
-
홀수 개수 :=0
-
본 각 키 값 쌍에 대해 수행
-
값이 홀수이면
-
홀수 개수 :=홀수 개수 + 1
-
-
odd_count가 2와 같으면
-
거짓을 반환
-
-
-
참을 반환
-
주요 방법에서 다음을 수행하십시오 -
-
스왑 :=0
-
util(s)이 참이면
-
왼쪽 :=0
-
오른쪽 :=s의 크기 - 1
-
s :=s
에서 가져온 새 문자 목록 -
왼쪽 <오른쪽, 하는 동안
-
s[left]가 s[right]와 같지 않으면
-
k :=오른쪽
-
k> 왼쪽 및 s[k]가 s[왼쪽]과 같지 않은 동안 수행
-
k :=k - 1
-
-
k가 왼쪽과 같으면
-
스왑 :=스왑 + 1
-
s[왼쪽], s[왼쪽 + 1] :=s[왼쪽 + 1], s[왼쪽]
-
-
그렇지 않으면
-
동안 k <오른쪽, 수행
-
스왑 s[k], s[k + 1]
-
k :=k + 1
-
스왑 :=스왑 + 1
-
-
왼쪽 :=왼쪽 + 1
-
오른쪽 :=오른쪽 - 1
-
-
-
그렇지 않으면
-
왼쪽 :=왼쪽 + 1
-
오른쪽 :=오른쪽 - 1
-
-
-
반품 교환
-
-
반환 -1
예시(파이썬)
이해를 돕기 위해 다음 구현을 살펴보겠습니다. −
class Solution:
def solve(self, s):
def util(s):
seen = {}
for i in s:
seen[i] = seen.get(i, 0) + 1
odd_count = 0
for k, val in seen.items():
if val & 1 == 1:
odd_count += 1
if odd_count == 2:
return False
return True
swaps = 0
if util(s):
left = 0
right = len(s) - 1
s = list(s)
while left < right:
if s[left] != s[right]:
k = right
while k > left and s[k] != s[left]:
k -= 1
if k == left:
swaps += 1
s[left], s[left + 1] = s[left + 1], s[left]
else:
while k < right:
s[k], s[k + 1] = s[k + 1], s[k]
k += 1
swaps += 1
left += 1
right -= 1
else:
left += 1
right -= 1
return swaps
return -1
ob = Solution()
s = "xxyy"
print(ob.solve(s)) 입력
"xxyy"
출력
2