문자열이 있다고 가정합니다. 문자열에서 문자를 삭제하거나 섞어서 생성할 수 있는 가장 긴 회문을 찾아야 합니다. 회문이 하나 이상 있으면 하나만 반환합니다.
따라서 입력이 pqqprrs와 같으면 출력은 pqrsrqp가 됩니다.
-
이 문제를 해결하기 위해 다음 단계를 따릅니다. −
-
count :=0으로 채워진 크기 256의 배열
-
범위 0에서 문자열 크기까지의 i에 대해
-
count[ASCII of(string[i]) ] :=count[ASCII of(string[i]) ] + 1
-
-
begin :=빈 문자열, mid :=빈 문자열, end :=빈 문자열
-
문자 :=ASCII of('a')
-
동안 문자 <=ASCII of('z') , 수행
-
count[character] AND 1이 0이 아닌 경우
-
중간 :=문자
-
개수[문자] :=개수[문자] - 1
-
문자 :=문자 - 1
-
-
그렇지 않으면
-
범위 0에서 count[character]/2(정수 나누기)의 i에 대해
-
시작 :=시작 + 문자 from (문자)
-
-
-
문자 :=문자 + 1
-
-
끝 :=시작
-
끝 :=역 끝
-
반환 시작 (중간) 연결 끝에서 문자 연결
예
이해를 돕기 위해 다음 구현을 살펴보겠습니다. −
def get_palindrome(string):
count = [0]*256
for i in range(len(string)):
count[ord(string[i])] += 1
begin = ""
mid = ""
end = ""
character = ord('a')
while character <= ord('z'):
if (count[character] & 1):
mid = character
count[character] -= 1
character -= 1
else:
for i in range(count[character]//2):
begin += chr(character)
character += 1
end = begin
end = end[::-1]
return begin + chr(mid) + end
string = "pqqprrs"
print(get_palindrome(string)) 입력
"pqqprrs"
출력
pqrsrqp