[자바 알고리즘 인터뷰] 6장 문자열 처리(1) 유효한 팰린드롬

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

 

- 주어진 문자열이 팰린드롬인지 확인하라. 대소문자를 구분하지 않으며, 영숫자(영문자와 숫자)만을 대상으로 한다. 

 

풀이 1) 문자 단위로 추출해서 처리 

 

 

- Character 클래스에는 원시 자료형 char를 입력값으로 하여 모두 소문자로 변경해주는 toLowerCase() 메소드와 영숫자인지 판별해주는 isLetterOrDigit() 메소드가 모두 존재한다.

 

ex)

Character.toLowerCase('G');
//'g'

Character.isLetterOrDigit('G');
//true

 

 

- 문자열에서 맨앞의 문자와 맨 뒤의 문자를 추출한 다음 유효한 문자(영숫자)인지를 확인하고 모두 소문자로 변경한 뒤에 일치 여부를 판단하면 된다. 

- 그렇게 맨 앞에서는 한 칸씩 뒤로, 맨 뒤에서는 한 칸씩 앞으로 서로를 향해 계속 비교하면서 중앙으로 이동해 나가다가, 겹치는 지점에 무사히 도달한다면 해당 문자열은 팰린드롬이라고 판별할 수 있다. 

 

class Solution {
    public boolean isPalindrome(String s) {
        int start =0;
        int end = s.length()-1;

        //서로 중앙으로 이동해 나가다 겹치는 지점에 도달하는 종료 
        while(start<end)
        {
            //영숫자인지 판별하고 유효하지 않으면 한 칸씩 이동
            if(!Character.isLetterOrDigit(s.charAt(start))) {
                start++;
            }else if(!Character.isLetterOrDigit(s.charAt(end))) {
                end--;
            }else {
                //유효한 문자라면 앞 글자와 뒷글자를 모두 소문자로 변경하여 비교
                if((Character.toLowerCase(s.charAt(start))!= Character.toLowerCase(s.charAt(end))))
                {
                    //하나라도 일치하지 않는다면 팰린드롬이 아니므로 false를 리턴
                    return false;
                }

                //앞쪽 문자는 한칸 뒤로, 뒤쪽문자는 한 칸 앞으로 이동
                start++;
                end--;
            }
        }

        //무사히 종료될 경우 팰린드롬이므로 true 리턴 
        return true;
    }
}

 

실행시간 : 5ms

 

풀이 2) 문자열 직접 비교 

 

- 문자 단위로 추출하지 않고, 문자열을 직접 비교해서 풀이

- String 클래스는 문자열을 치환할 수 있는 몇 가지 메소드를 제공하며, 그 중에는 replaceAll()처럼 정규식을 지원하는 메소드도 있다. 

 

ex)

String s ="Do geese see God?";
s.replaceAll("[^A-Za-z0-9]","").toLowerCase();
//"dogeeseseegod"

 

- 문자열을 문자 단위로 추출하지 않고도 유효한 문자로 걸러낸 다음 한꺼번에 모두 소문자로 변경할 수 있다. 

- 팰린드롬 여부를 확인하기 위해 문자열을 뒤집어서 확인

 

- StringBuilder는 reverse()라는 뒤집는 메소드를 제공하며, 이후 toString()을 이용해 String으로 변경하면 이제 원래 문자열과 동일한 자료형이 되어 서로 값을 비교할 수 있다. 

 

ex)

new StringBuilder("god").reverse().toString();
//"dog"

 

 

class Solution {
    public boolean isPalindrome(String s) {
       //정규식으로 유효한 문자만 추출한 다음 모두 소문자로 변경
       String s_filtered = s.replaceAll("[^A-Za-z0-9]","").toLowerCase();

       //문자열을 뒤집은 다음 String으로 변경
       String s_reversed = new StringBuilder(s_filtered).reverse().toString();

       //두 문자열이 동일한지 비교 
       return s_filtered.equals(s_reversed);
    }
}

 

실행시간 : 796ms