문자열의 문자가 Python의 O(1) 추가 공간에서 회문을 형성하는지 확인하십시오.

문자열 s가 있다고 가정합니다. 이 문자열에는 소문자, 기타 특수 문자 및 숫자가 포함될 수 있습니다. 문자열에 있는 문자만 회문인지 여부를 확인해야 합니다. 여기서 한 가지 제약 조건은 이 문제를 해결하기 위해 추가 공간을 사용할 수 없다는 것입니다.

따라서 입력이 s ="ra$5ce58car"와 같으면 문자가 회문인 "racecar"를 형성하므로 출력은 True가 됩니다.

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

• first_letter_index() 함수를 정의합니다. str, 왼쪽, 오른쪽이 필요합니다.
• 색인:=-1
• 왼쪽에서 오른쪽으로 + 1 범위의 i에 대해
  • str[i]가 소문자 알파벳이면
    • 인덱스 :=나
    • 루프에서 나오다
• 반환 인덱스
• last_letter_index() 함수를 정의합니다. str, 왼쪽, 오른쪽이 필요합니다.
• 색인:=-1
• 왼쪽에서 오른쪽으로 범위 내 i의 경우 - 1, 1 감소, do
  • str[i]가 소문자 알파벳이면
    • 인덱스 :=나
    • 루프에서 나오다
  • 반환 인덱스
  • 기본 방법에서 다음을 수행합니다.
  • 왼쪽 :=0, 오른쪽 :=str의 크기 - 1
  • 플래그 :=참
  • 범위 0에서 str 크기까지의 i에 대해
    • left :=first_letter_index(str, 왼쪽, 오른쪽)
    • 오른쪽 :=last_letter_index(str, 오른쪽, 왼쪽)
    • 오른쪽 <0 또는 왼쪽 <0이면
      • 루프에서 나오다
    • str[left]가 str[right]와 같으면
      • 왼쪽 :=왼쪽 + 1
      • 오른쪽 :=오른쪽 - 1
      • 다음 반복으로 이동
    • 플래그 :=거짓
      • 루프에서 나오다
• 반환 플래그

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

예시 코드

def first_letter_index(str, left, right):
   index = -1
   for i in range(left, right + 1):
      if str[i] >= 'a' and str[i] <= 'z' :
         index = i
         break
 
   return index

def last_letter_index(str, left, right):
   index = -1
   for i in range(left, right - 1, -1) :
      if str[i] >= 'a' and str[i] <= 'z':
         index = i
         break
 
   return index

def solve(str):
   left = 0
   right = len(str) - 1
   flag = True
 
   for i in range(len(str)) :
      left = first_letter_index(str, left, right)
      right = last_letter_index(str, right, left)
 
      if right < 0 or left < 0:
         break
      if str[left] == str[right]:
         left += 1
         right -= 1
         continue
 
      flag = False
      break
 
   return flag
 
s = "ra$5ce58car"
print(solve(s))

입력

"ra$5ce58car"

출력

True