[LeetCode] 125. Valid Palindrome - Java[자바]

링크

문제

모든 대문자를 소문자로 변환하고 영숫자가 아닌 문자를 모두 제거한 후 앞뒤가 같은 경우 구문은 팔린드롬입니다. 영숫자 문자에는 문자와 숫자가 포함됩니다.

문자열 s가 주어지면 팔린드롬이면 참을 반환하고, 그렇지 않으면 거짓을 반환합니다.

풀이

투포인터가 아닌 그냥 문자열을 바꿔서 풀게되면 다음과 같은 풀이를 생각할 수 있다.

class Solution {  
  
    public boolean isPalindrome(String s) {  
        String modifiedString = s.toLowerCase().replaceAll("[^a-z0-9]", "");  
        for (int i = 0; i < modifiedString.length() / 2; i++) {  
            if (modifiedString.charAt(i) != modifiedString.charAt(modifiedString.length() - i - 1)) {  
                return false;  
            }  
        }  
        return true;  
    }  
}

class Solution {  
  
    public boolean isPalindrome(String s) {  
        if (s == null || s.isEmpty()) {  
            return true;  
        }  
        int left = 0;  
        int right = s.length() - 1;  
        while (left < right) {  
            while (left < right && !Character.isLetterOrDigit(s.charAt(left))) {  
                left++;  
            }  
            while (left < right && !Character.isLetterOrDigit(s.charAt(right))) {  
                right--;  
            }  
            if (Character.toLowerCase(s.charAt(left)) != Character.toLowerCase(s.charAt(right))) {  
                return false;  
            }  
            left++;  
            right--;  
        }  
        return true;  
    }  
}

• 두개의 포인터를 활용하여 좌우 index에 해당하는 문자를 서로 비교하여 팰린드롬인지 확인한다.
• Charactor의 isLetterOrDigit메서드를 활용하였다.

public static boolean isLetterOrDigit(int codePoint) {  
    return ((((1 << Character.UPPERCASE_LETTER) |  // 1
        (1 << Character.LOWERCASE_LETTER) |        // 2
        (1 << Character.TITLECASE_LETTER) |        // 3
        (1 << Character.MODIFIER_LETTER) |         // 4
        (1 << Character.OTHER_LETTER) |            // 5
        (1 << Character.DECIMAL_DIGIT_NUMBER)) >> getType(codePoint)) & 1) // 9
        != 0;  
}

isLetterOrDigit의 구현을 보게되면 우리가 넘겨준 char를 int로 형변환 하여, 해당 문자의 유니코드에 대한 연산을 하는 것을 볼 수 있다.
상수들은 각각 주석으로 해당 값을 적어두었다.

• 문제에서 non-alphanumeric characters으로 주어진다고 했으므로, 굳이 isLetterOrDigit이 아닌 다음과 같이 직접 해당 문자가 영어 대문자, 소문자인지 숫자인지를 확인하는 로직을 이용하여 구현할 수 있다.

class Solution {  
  
    public boolean isPalindrome(String s) {  
        if (s == null || s.isEmpty()) {  
            return true;  
        }  
        int left = 0;  
        int right = s.length() - 1;  
        while (left < right) {  
            while (left < right &&  
                   !((s.charAt(left) >= 65 && s.charAt(left) <= 90) ||  
                     (s.charAt(left) >= 97 && s.charAt(left) <= 122) ||  
                     (s.charAt(left) >= 48 && s.charAt(left) <= 57))) {  
                left++;  
            }  
            while (left < right &&  
                   !((s.charAt(right) >= 65 && s.charAt(right) <= 90) ||  
                     (s.charAt(right) >= 97 && s.charAt(right) <= 122) ||  
                     (s.charAt(right) >= 48 && s.charAt(right) <= 57))) {  
                right--;  
            }  
            if (Character.toLowerCase(s.charAt(left)) != Character.toLowerCase(s.charAt(right))) {  
                return false;  
            }  
            left++;  
            right--;  
        }  
        return true;  
    }  
}

다음은 가독성을 위해 위 코드를 메서드 추출한 코드이다.

class Solution {  
  
    private boolean isLetterOrDigit(char c) {  
        return (c >= 65 && c <= 90) || (c >= 97 && c <= 122) || (c >= 48 && c <= 57);  
    }  
  
    public boolean isPalindrome(String s) {  
        if (s == null || s.isEmpty()) {  
            return true;  
        }  
        int left = 0;  
        int right = s.length() - 1;  
        while (left < right) {  
            while (left < right && !isLetterOrDigit(s.charAt(left))) {  
                left++;  
            }  
            while (left < right && !isLetterOrDigit(s.charAt(right))) {  
                right--;  
            }  
            if (Character.toLowerCase(s.charAt(left)) != Character.toLowerCase(s.charAt(right))) {  
                return false;  
            }  
            left++;  
            right--;  
        }  
        return true;  
    }  
}

대문자, 소문자, 숫자의 ASCII 코드는 자주 사용되므로 익혀두는 것이 좋다.