문자열 s가 주어졌을 때, 이 문자열의 모든 회문(palindrome) 부분 문자열의 길이가 홀수인지 확인하는 문제입니다.
예를 들어 입력이 s = "level"이라면, 출력은 True가 됩니다. "level"의 회문 부분 문자열인 "l", "e", "v", "eve", "level"은 모두 길이가 홀수이기 때문입니다.
접근 방법
이 문제의 핵심 아이디어는 매우 간단합니다. 문자열에 같은 문자가 연속해서 나타난다면, 그 두 문자 자체가 길이 2짜리 회문 부분 문자열(짝수 길이)이 됩니다.
따라서 해결 절차는 다음과 같습니다.
- 인덱스 1부터 문자열 길이까지 반복합니다.
- s[i]와 s[i-1]이 같은 문자라면, 짝수 길이의 회문이 존재하므로 False를 반환합니다.
- 반복이 끝날 때까지 같은 인접 문자가 없다면 True를 반환합니다.
이 알고리즘은 한 번의 순회만 필요하므로 시간 복잡도는 O(n), 공간 복잡도는 O(1)로 매우 효율적입니다.
구현 예제
class Solution:
def solve(self, s):
for i in range(1, len(s)):
if s[i] == s[i - 1]:
return False
return True
ob = Solution()
s = "level"
print(ob.solve(s))
입력
"level"
출력
True
"level"에는 같은 문자가 인접해 있지 않으므로, 길이 2 이상의 짝수 회문 부분 문자열이 존재할 수 없습니다. 따라서 결과는 True입니다. 반면 "abba"처럼 "bb"와 같이 동일한 문자가 붙어 있는 경우에는 False가 반환됩니다.