[LeetCode] 125. Valid Palindrome 풀이 (Java)

✔️ 오늘의 리트코드 공부 기록 – Valid Palindrome

---

 

문제 요약 (Valid Palindrome)

문자열이 주어질 때,
알파벳과 숫자만 고려하여 (대소문자는 무시) 문자열이 회문(Palindrome)인지 판별하라.

문제링크: https://leetcode.com/problems/valid-palindrome/

---

 

🤔 처음 떠올린 아이디어

처음엔 이렇게 생각했다.

공백이랑 특수문자를 다 제거해서
새 배열을 하나 만들고, 뒤집어서 비교하면 되지 않을까?

 

즉,

1. 문자열 정제
2. 새 문자열 생성
3. reverse 해서 비교

이 방식은 직관적이지만 어딘가 찝찝했다.

“굳이 새 배열을 꼭 만들어야 하나?”

---

 

💡 회문은 결국

👉 앞과 뒤가 같은지 비교하는 문제다.

 

그렇다면

굳이 정제된 문자열을 새로 만들지 않아도
양쪽에서 동시에 검사하면 되지 않을까?

회문 문제는 거의 공식처럼 등장하는 패턴이 있다.

Left → ← Right

양쪽에서 시작해서 중앙으로 좁혀오는 방식이다.

여기서 추가 조건만 처리해주면 된다.

• 알파벳/숫자 아니면 건너뛰기
• 대소문자 통일
• 다르면 바로 false

---

🔎 알고리즘 흐름 정리

1. left = 0, right = n-1
2. left < right 동안 반복
3. 특수문자는 건너뛴다
4. 대소문자 무시하고 비교
5. 다르면 false
6. 끝까지 통과하면 true

---

코드(Java)

class Solution {
    public boolean isPalindrome(String s) {

        int left = 0;
        int right = s.length() - 1;

        while (left < right) {

            while (left < right && 
                   !Character.isLetterOrDigit(s.charAt(left))) {
                left++;
            }

            while (left < right && 
                   !Character.isLetterOrDigit(s.charAt(right))) {
                right--;
            }

            if (Character.toLowerCase(s.charAt(left)) !=
                Character.toLowerCase(s.charAt(right))) {
                return false;
            }

            left++;
            right--;
        }

        return true;
    }
}

 

📈 시간 / 공간 복잡도

• 시간: O(N)
• 공간: O(1)

각 문자를 최대 한 번씩만 확인한다.

---

정규식 풀이

String cleaned = s.replaceAll("[^a-zA-Z0-9]", "").toLowerCase();
return cleaned.equals(new StringBuilder(cleaned).reverse().toString());

 

이 방식은

• 코드가 짧다
• 직관적이다
• 대신 O(N) 공간 사용

인터뷰에서는 보통
👉 O(1) 공간 풀이를 더 선호한다.

---

📝 이번 문제에서 얻은 깨달음

• 회문 문제는 “문자열 문제”가 아니라 “투 포인터 문제”다.
• 문자열을 새로 만들지 말고 조건을 이동 과정에서 처리하자.