A phrase is a palindrome if, after converting all uppercase letters into lowercase letters and removing all non-alphanumeric characters, it reads the same forward and backward. Alphanumeric characters include letters and numbers.
Given a string s
, return true
if it is a palindrome, or false
otherwise.
s.length
<= 2 * 10^5s
consists only of printable ASCII characters.class Solution:
def isPalindrome(self, s: str) -> bool:
아스키코드로 표현가능한 문자로만 이루어진 문자열 s
가 주어집니다. 여기서 알파벳과 숫자를 제외했을 때, 팰린드롬을 이루는지 여부를 bool
값으로 반환하는 문제입니다.
제가 생각한 코드는 다음과 같습니다.
class Solution:
def isPalindrome(self, s: str) -> bool:
start_idx,end_idx = 0,len(s)-1
while start_idx < end_idx:
while not s[start_idx].isalnum() and start_idx < end_idx: start_idx +=1
while not s[end_idx].isalnum() and start_idx < end_idx : end_idx -=1
if s[start_idx].lower() != s[end_idx].lower():
return False
start_idx += 1
end_idx -= 1
return True
start_idx
, end_idx
: 대칭을 확인할 앞, 뒤 문자의 인덱스 변수입니다.while
문의 조건은 서로의 인덱스가 지나치지 않는 것으로 합니다.start_idx
는 올리고 end_idx
값은 내리며 조정합니다.lower()
을 통해 소문자로 변환한 값이 같은지 비교합니다.False
를 반환합니다.True
를 반환합니다.조건문에서 최대 길이가 200,000까지 나오기 때문에 O(n)으로 해결해야 하는 것을 알 수 있었습니다.
알파벳과 숫자 외의 문자를 지나쳐야 하는 부분에서 인덱스의 대칭이 깨지므로 최소 두 개의 인덱스 변수가 필요하다는 방향을 잡았습니다.
약간의 편법(?)으로 풀었던 부분을 고백하자면 예외 부분을 크게 신경쓰지 않고 코드를 작성했습니다. 문자열의 길이가 1이거나 알파벳이나 숫자가 아닌 문자열로 이루어져 있거나..
테스트케이스를 통해 고쳐야지 했는데 잘 통과했네요 하핳