Python에서 사전식으로 가장 작은 비 회문 문자열을 찾는 프로그램

회문인 문자열 s가 있다고 가정합니다. s가 더 이상 회문이 아니고 사전순으로 가장 작도록 한 문자를 변경해야 합니다.

따라서 입력이 s ="level"과 같으면 출력은 "aevel"이 됩니다. 첫 번째 "l"을 "a"로 변경하여 회문(palindrome)이 아닌 사전순으로 가장 작은 문자열을 얻을 수 있기 때문입니다.

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

• 범위 0에서 정수 부분(s / 2의 크기)에 대해 다음을 수행합니다.
  • s[i]가 "a"와 같지 않으면
    • s :=s에 있는 모든 문자의 새 목록
    • s[i] :="아"
    • s의 모든 문자를 결합하고 반환
• s :=s에 있는 모든 문자의 새 목록
• s의 마지막 요소 :="b"
• s의 모든 문자를 결합하고 반환

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

예시

class Solution:
   def solve(self, s):
      for i in range(len(s) // 2):
         if s[i] != "a":
            s = list(s)
            s[i] = "a"
            return "".join(s)
      s = list(s)
      s[-1] = "b"
      return "".join(s)
ob = Solution()
s = "level"
print(ob.solve(s))

입력

"level"

출력

aevel