Leet code (Easy): 125. Valid Palindrome (투 포인터) - Java

 

20. Valid Parentheses 문제를 풀때는 괄호가 선입후출로 다 닫히는지 보는문제였기 때문에 Stack을 사용했다.

그러나 이문제는 Palindrome 문제로

문자, 기호, 숫자 등이 포함된 문자열에서 문자와 숫자가 대칭을 이루는지 확인하는 문제이다.

 

따라서 Stack을 사용하기보다 투 포인터로 가장자리부터 문자와 숫자를 만나면 두 포인터가 가리키는 문자/숫자가 일치하는지 확인하는 방식으로 진행하는 것이 공간복잡도는 O(1)이고, 시간복잡도는 O(N) 으로 효율적이다.

 

class Solution {
    public boolean isPalindrome(String s) {
        if(s.isEmpty()){
            return true;
        }

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

        while(left <= right){
            char currLeft = s.charAt(left);
            char currRight = s.charAt(right);
            if(!Character.isLetterOrDigit(currLeft)){
                left++;
            } else if(!Character.isLetterOrDigit(currRight)){
                right--;
            } else{
                if(Character.toLowerCase(currLeft) != Character.toLowerCase(currRight)){
                    return false;
                }

                left++;
                right--;
            }
        }

        return true;
    }
}