125. Valid Palindrome

난이도: 중간 (Medium)

링크: LeetCode 125

풀이 날짜: 2025/10/22

 

1. 문제 이해

문자열에서 알파벳과 숫자만 고려하고, 대소문자 구분 없이 회문(Palindrome.  뒤집었을때 원문과 동일한지) 여부를 판단하는 문제.

 

 

2. 풀이 방법 비교

방법 1 — 전체 전처리 후 뒤집기

var isPalindrome = function(s) {
  const string = s.replace(/[^0-9a-zA-Z]/g, '').toLowerCase();
  const reverse = string.split('').reverse().join('')
  return string === reverse
};

• 정규식을 이용해 알파벳/숫자만 남김
• 모두 소문자로 변환 후 뒤집기
• 마지막에 문자열 비교

장점: 코드 간결, 이해 쉽다

단점:

1. 문자열 전체를 새로 생성 → O(n) 공간
2. 문자열 뒤집기 split('') + reverse + join('') → O(n) 시간
3. 결과적으로 총 O(n) 시간 & O(n) 공간

방법 2 — 투 포인터(Left/Right) 직접 비교

function isAlphaNumeric(char) {
  return /^[a-z0-9]$/i.test(char);
}

var isPalindrome = function(s) {
  let left = 0;
  let right = s.length - 1;

  while (left < right) {
    while (left < right && !isAlphaNumeric(s[left])) left++;
    while (left < right && !isAlphaNumeric(s[right])) right--;

    if (s[left].toLowerCase() !== s[right].toLowerCase()) return false;

    left++;
    right--;
  }

  return true;
};

• 문자열을 전처리하지 않고 원본에서 직접 비교
• 알파벳/숫자가 아닌 경우 건너뛰기
• 양쪽에서 동시에 비교하면서 회문 검사

장점:

1. 공간 효율적 → O(1) 추가 공간
2. 필요한 경우에만 문자를 소문자로 변환 → 불필요한 처리 없음
3. 시간 효율 좋음 → O(n), 상수 계수 작음

단점: 코드가 조금 더 길고 직관적이지 않을 수 있음

 

3. 핵심 포인트 비교

개념	방법 1: 뒤집기방법	2: 투 포인터
시간 복잡도	O(n)	O(n)
공간 복잡도	O(n)	O(1)
처리 방식	문자열 전처리 후 뒤집기	원본에서 투 포인터 비교
특징	코드 간결	메모리 효율적, 상수 계수 작음

 

 

4. 결론

• 작은 문자열, 간단한 문제 → 방법 1 사용 가능
• 대규모 문자열, 공간 효율 필요 → 방법 2 추천

투 포인터는 대부분 “연속 데이터 회문 검사” 문제에서 가장 효율적 패턴이다.