Valid Palindrome

문제

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

---

풀이

Alphanumeric charactor = 알파벳과 숫자를 포함

1. 우선 주어진 문자열을 소문자(LowerCase)로 만들고
2. 주어진 문자열을 배열 문자로 만든다
3. 문자 하나씩 비교하여 알파벳과 숫자가 아니라면 빈칸으로 만든다.
4. 해당 배열을 다시 문자열로 만들고, 빈칸을 모두 지운다.
5. 해당 문자열을 토대로 중앙에서 확장하여 팰린드롬인지 검사한다.

class Solution {
    public boolean isPalindrome(String s) {
        char [] chars = s.toLowerCase().toCharArray();
        checkIsLetter(chars);
        String result = new String(chars).replaceAll(" ", "");

        int len = result.length();
        
        if (len == 1) return true;
        if (len == 2) return result.charAt(0) == result.charAt(1);

        int left, right;
        if (len % 2 == 0) {
            left = len / 2 - 1;
            right = left + 1;
        } else {
            left = len / 2;
            right = left;
        }

        return checkIsPalindrome(result, left, right);
    }

    private void checkIsLetter(char [] chars) {
        for (int i=0; i<chars.length; i++) {
            if (!(('a' <= chars[i] && chars[i] <= 'z') || ('0' <= chars[i] && chars[i] <= '9'))) {
                chars[i] = ' ';
            }
        }
    }

    private boolean checkIsPalindrome(String s, int left, int right) {
        boolean result = true;
        while ( left >= 0 && right < s.length()) {
            if (s.charAt(left) != s.charAt(right)) {
                result = false;
                break;
            }
            left--;
            right++;
        }
        return result;
    }
}

11ms 경과

놓친 부분

팰린드롬을 검사할 때.. 중앙부터 하지 않고, 양쪽 끝에서 시작하면 된다.
왜냐하면 이 문자열이 팰린드롬 인지, 아닌지만 확인하면 되기 때문..!

따라서 코드를 조금 변경해봤다.

class Solution {
    public boolean isPalindrome(String s) {
        char [] chars = s.toLowerCase().toCharArray();
        checkIsLetter(chars);
        String result = new String(chars).replaceAll(" ", "");

        int len = result.length();
        
        if (len == 1) return true;
        if (len == 2) return result.charAt(0) == result.charAt(1);

        return checkIsPalindrome(result, 0, len - 1); //변경된 부분
    }

    private void checkIsLetter(char [] chars) {
        for (int i=0; i<chars.length; i++) {
            if (!(('a' <= chars[i] && chars[i] <= 'z') || ('0' <= chars[i] && chars[i] <= '9'))) {
                chars[i] = ' ';
            }
        }
    }

	//변경된 함수, left과 right가 점점 가까워지는 모양새
    private boolean checkIsPalindrome(String s, int left, int right) {
        boolean result = true;
        while ( left <= right ) {
            if (s.charAt(left) != s.charAt(right)) {
                result = false;
                break;
            }
            left++;
            right--;
        }
        return result;
    }
}

10ms 초과

여기서 더 줄여보자.

left와 right의 범위를 양끝에서 중간으로 좁혀가면서
동시에 Alphanumeric charactor(알파벳 & 숫자)인지를 확인하는 것이다.
만약 Alphanumeric 하지 않다면 left나 right를 더 좁혀가게 된다.

그리고 마지막 Alphanumeric한 left와 right의 문자를 확인할 때,
UpperCase라면 LowerCase로 변경하여 비교한다.

즉, 미리 Alphanumeric character로 변경해놓고 팰린드롬인지 확인하는 것이 아닌,
팰린드롬인지 확인하면서 Alphanumeric character인지도 확인하는 것이다.

한 번에 모든 과정을 처리할 수 있으니 속도가 매우 빠를 것이다.

예를 들어서 "A man, nama" 라고 주어졌다고 생각해보자.

left와 right의 시작 인덱스는 각각 0, 9(길이 - 1) 이다.

1. left = "A", right = "a" 모두 Alphanumeric하다.
   비교할 때, left가 UpperCase이므로
   left의 A를 a로 변경하여 비교하기 때문에 통과한다.

2. left = " ", right = "m", left가 Alphanumeric하지 않다.
   따라서 left를 하나 더 상승시킨다.

3. left = "m", right = "m", 모두 Alphanumeric하다.
   모두 LowerCase이기 때문에 바로 비교하게 되고, 같은 문자이므로 통과한다.

이런 방식으로 left와 right이 서로를 넘지 않는 범위까지 (left < right) 서로 비교한다.

class Solution {
    public boolean isPalindrome(String s) {
        int len = s.length();
        return checkIsPalindrome(s, 0, len - 1);
    }

    private boolean checkIsPalindrome(String s, int left, int right) {
        boolean result = true;
        while ( left <= right ) {

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

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

            char leftChar = isLower(s.charAt(left));
            char rightChar = isLower(s.charAt(right));

            if (leftChar != rightChar) {
                result = false;
                break;
            }
            left++;
            right--;
        }
        return result;
    }

    private char isLower(char c){
        if (Character.isUpperCase(c)){
            return (char) (c + 32);
        }
        else return c;
    }

    private boolean isAlphanumeric(char c) {
        //알파벳이나 Digit이 아니면
        return Character.isAlphabetic(c) || Character.isDigit(c);
    }
}

3ms 🫨🫨🫨

그리고 여기서는 찾아보니 Character 참조형 변수를 사용하면 여러 메서드를 사용할 수 있다.
isUpperCase() , isDigit() , isAlphabetic() .. 등등 편한 메스드들이 있지만, 아무래도 힙 메모리(Heap)에 저장되는 참조형 변수이기 때문에 기본형보다 상대적으로 느릴 것이다.

마지막으로 기본형 변수를 처리하기 위해 비교연산자를 사용하여 조건문을 수정해보자.

기본형 변수 사용

class Solution {
    public boolean isPalindrome(String s) {
        int len = s.length();
        char [] chars = s.toCharArray();
        return checkIsPalindrome(chars, 0, len - 1);
    }

    private boolean checkIsPalindrome(char[] chars, int left, int right) {
        boolean result = true;
        while ( left <= right ) {

            while (left < right && !isAlphanumeric(chars[left])) {
                left ++;
            }

            while ( left < right && !isAlphanumeric(chars[right])) {
                right --;
            }

            char leftChar = isLower(chars[left]);
            char rightChar = isLower(chars[right]);

            if (leftChar != rightChar) {
                result = false;
                break;
            }
            left++;
            right--;
        }
        return result;
    }

	//아래의 메서드 모두 기본형 변수로 비교하는 연산으로 변경
  
    private char isLower(char c){
        if ('A' <= c && c <= 'Z'){
            return (char) (c + 32);
        }
        else return c;
    }

    private boolean isAlphanumeric(char c) {
        //알파벳이나 Digit이 아니면
        return ('A' <= c && c <= 'Z') || ('a' <= c && c <= 'z') || ('0' <= c && c <= '9');
    }
}

미약하지만 그래도 2ms 까지 도달하였다!