leetcode top interview 150 | Valid Palindrome | Two Pointer

 

Question

 

문장이 펠린드롬이려면 

1. 모든 대문자는 소문자로 변환

2. 알파벳과 숫자가 아닌 것은 제거 

3. 앞쪽에서 읽었을때와 뒷쪽에서 읽었을때가 동일해야함

 

주어진 문자열이 펠린드롬이면 true, 아니면 false로 리턴

 

Accepted Code - Two Pointer

class Solution {
    public boolean isPalindrome(String s) {
        s = s.toLowerCase(); // 1번조건 
        
        int left = 0;
        int right = s.length() - 1;
        
        while(left<right){
            char first = s.charAt(left);
            char last = s.charAt(right);

			// 2번조건 
            if(!isValidChar(first)){
                left++;
                continue;
            }

            if(!isValidChar(last)){
                right--;
                continue;
            }
            
			// 3번조건 
            if(first == last){
                left++;
                right--;
                continue;
            }else{
                return false;
            }
        }
            
        return true;
    }
    private boolean isValidChar(char c){// 알파벳 소문자이거나 숫자여야 함
        if((c >= 'a' && c <= 'z') || (c >= '0' && c <= '9')) return true;
        else 
            return false;
    }
}

 

Accepted Code - Using StringBuilder

class Solution {
    public boolean isPalindrome(String s) {
        s = s.toLowerCase();// 1번조건
        s = s.replaceAll("[^a-z0-9]", "");// 2번조건
        StringBuilder sb = new StringBuilder(s);
        if(sb.toString().equals(sb.reverse().toString()))// 3번조건
            return true;
        else
            return false;
    }
}

 

Solve

 

#1

앞 뒤로 문자가 같아야 하기 때문에 문자열의 양 끝으로 인덱스를 설정하고 왼쪽을 증가, 오른쪽을 감소해가며 해당 문자들이 같은지 비교하는 방식이 떠올랐다. 

 

Two Pointer : 투 포인터 알고리즘 
- 선형 구조에서 두개의 포인터를 움직여 가며 조건을 충족시키는 값을 찾을 때 이용
- O(N)의 시간복잡도 

 

문자열의 시작 인덱스를 left로, 마지막 인덱스를 right으로 놓고 해당 위치의 문자가 유효한지 체크한다. 

유효하지 않은 문자면 다음 위치의 문자를 탐색해야하므로 left는 증가시키고 right는 감소시킨다. 

유효한 문자여도 두개의 문자가 동일하지 않으면 바로 false를 리턴한다. 

 

유효문자 체크는 다른 메소드로 분리하였다.

 

 

#2 

주어진 문자열과 거꾸로 한 문자열이 동일해야하기 때문에 StringBuilder에 있는 reverse() 메서드가 떠올랐다. 

대문자를 소문자로 변환하기 위해 toLowerCase를 사용하고, a~z 또는 0-9가 아닌 다른 문자들은 제거(^)하기 위해 replaceAll을 사용했다.

원본 문자열인 s를 builder에 넣고 reverse와 한 문자열과 같으면 true를 리턴, 같지 않으면 false를 리턴한다.

 

 

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

Valid Palindrome - LeetCode