문자열 조작_1. Valid Palindrome

leetcode 125. Valid Palindrome

문제

주어진 문자열이 팰린드롬인지 확인하라. 대소문자를 구분하지 않으며, 영문자와 숫자만을 대상으로 한다.

입출력예시

• 입력: "A man, a plan, a canal: Panama"
• 출력: true

• 입력: "race a car"
• 출력: false

풀이

팰린드롬(Palindrome)이란 앞뒤가 같은 단어나 문장이다. 이를 구하기 위해선 다음과 같이 다양한 방법을 사용할 수 있다.

파이썬

리스트로 변환

def isPalindrome(self, s: str) -> bool:
    strs = []
    # 전처리 
    for char in s:
        if char.isalnum(): # 영문자, 숫자 판별
            strs.append(char.lower()) # 소문자 변환 후 추가
            
    # 팰린드롬 여부 판단        
    while len(strs) > 1: 
        if strs.pop(0) != strs.pop():
            return False
            
    return True

• runtime: 288 ms
• memory: 19.6 MB

슬라이싱 사용

def isPalindrome(self, s: str) -> bool:
    s = s.lower() // 소문자 변환
    s = re.sub('[^a-z0-9]', '', s) # 정규식 필터링
    
    return s == s[::-1] # 문자열 슬라이싱 사용 

• runtime: 32 ms
• memory: 15.6 MB

[::-1]를 사용한 것이 특징으로, 문자열을 다음과 같이 뒤집어준다.
안녕하세요 -> 요세하녕안

자바스크립트

const isPalindrome = s => {
  s = s.toLowerCase(); // 소문자 변환
  s = s.replace(/[^a-z0-9]/gi,''); // 정규식 필터링
  
  for (let i = 0, j = s.length - 1; i <= j; i++, j--) {
    if (s.charAt(i) !== s.charAt(j)) {
      return false;
    }
  }
  return true;
}

• runtime: 88 ms
• memory: 41.2 MB

반복문 안에서 두 변수가 반대로 진행되는 것이 특징이다. condition에서 두 변수가 만나면 중단된다.

참고
파이썬 알고리즘 인터뷰