[LeetCode/Java] 125. Valid Palindrome

0. 문제

https://leetcode.com/problems/valid-palindrome/

1. 문제 설명

• 문자열 s가 주어질 때 해당 문자열이 팰린드롬이면 true를 반환하고, 아닌 경우 false를 반환하라.
• 팰리드롬이란, 문자열의 공백과 영숫자를 제거한 후 앞으로 읽었을 때와 뒤로 읽었을 때 같은 문자열이다.

2. 문제 풀이

2.1. 접근법

• 정규식을 사용해서 공백과 영숫자가 아닌 문자를 제거한다.

3. 코드

class Solution {
    public boolean isPalindrome(String s) {
        s = s.toUpperCase().replaceAll(" ", "").replaceAll("[^a-zA-Z0-9]|_", "");
        String tmp = new StringBuilder(s).reverse().toString();
        if (tmp.equals(s)) return true;
        else return false;
        
    }
}

4. 결과

5. 개선점

5.1. 투 포인터 적용

• 문제를 보자마자 String 메서드가 생각나서 빠르게 풀었지만, 런타임은 느렸다.
• 투 포인터를 사용하면 개선할 수 있다.
• 투 포인터 접근

  • 문자열의 양 끝부터 순서대로 비교한다.

  • 문자나 숫자가 아닌 경우(공백, 특수문자) 그 다음 인덱스의 문자를 비교한다.

  • 문자를 비교했을 때 다른 경우 팰리드롬이 아니기 때문에 false를 반환한다.

  • 모든 문자열의 비교가 끝나면 팰리드롬 문자열이기 때문에 true를 반환한다.

    class Solution {
        public boolean isPalindrome(String s) {       
            int li = 0;
            int ri = s.length() - 1;
            char[] charArr = s.toLowerCase().toCharArray();
    
            while (li <= ri) {
                if (!Character.isLetterOrDigit(charArr[li])) li++;
                else if (!Character.isLetterOrDigit(charArr[ri])) ri--;
                else if(charArr[li++] != charArr[ri--]) return false;
            }
            return true;
        }
    }

• 결과