[LeetCode] Valid Palindrome

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

 

A phrase is a palindrome if, after converting all uppercase letters into lowercase letters and removing all non-alphanumeric characters, it reads the same forward and backward. Alphanumeric characters include letters and numbers.

Given a string s, return true if it is a palindrome, or false otherwise.

 

Example 1:

Input: s = "A man, a plan, a canal: Panama"

Output: true

Explanation: "amanaplanacanalpanama" is a palindrome.

Example 2:

Input: s = "race a car"

Output: false

Explanation: "raceacar" is not a palindrome.

Example 3:

Input: s = " "

Output: true

Explanation: s is an empty string "" after removing non-alphanumeric characters.

Since an empty string reads the same forward and backward, it is a palindrome.

 

Constraints:

• 1 <= s.length <= 2 * 105
• s consists only of printable ASCII characters.

---

 

A problem that checks whether a given string is the same when reversed (i.e., a palindrome).

In this case, special characters and spaces are ignored, and only numbers and alphabetic characters are considered.

주어진 문자열에 대해 뒤집어도 동일한 글자인지 확인하는 문제.

이 때 숫자와 알파벳을 제외한 특수문자와 공백은 무시하고 진행한다.

 

I compared characters starting from the front and the end of the string, returning false if they didn’t match.

맨 앞에서부터 가장 끝에 있는 것끼리 비교해서 같은지 확인하고, 다르면 false를 리턴하도록 했다.

 

class Solution {
    public boolean isPalindrome(String s) {
        // 1. remove all letters that's not alphabet
        char[] ss = s.toCharArray();
        List<Integer> removed = new ArrayList();
        for(int ch:ss){
            // uppercase alphabet
            if(ch >= 65 && ch <= 90){
                removed.add(ch);
            }
            // lowercase alphabet : if it's difference is same to 32, it's same word
            if(ch >=97 && ch <= 122){
                removed.add(ch - 32);
            }
            // numerics
            if(ch >= 48 && ch <= 57){
                removed.add(ch);
            }
        }
        // 2. check if it's same with opposite one
        int loopCnt = removed.size()/2;
        for(int i=0; i < loopCnt ; i++){
            // compare 0 & lastOne, 1&former, 2&former,...
            if(removed.get(i) != removed.get(removed.size()-1-i)){
                return false;
            }
        }

        return true;
    }
}

 

To avoid edge cases like 0P, I didn’t simply treat characters as the same alphabet based on an ASCII code difference of 32. Instead, I handled this with explicit conditional checks. In the end, it passed successfully~_~

0P와 같은 경우를 제외하기 위해, 단순히 ASCII 코드값의 차이가 32가 된다고 해서 같은 알파벳으로 간주하지 않고, 별도의 조건문으로 처리했다. 결과적으로 잘 통과했다~_~

 

Of course, when considering scalability, it might be better to look for a different approach rather than adding more conditional statements like that.

the solution can be improved by switching to a two-pointer approach and avoiding list creation altogether,
simply moving the pointers whenever a character is not a digit or an alphabet letter.

This way, it can be implemented like below as well.

물론, 확장성을 고려했을 때에는 저런 식으로 조건문을 추가하기보단 다른 방법을 찾는 게 더 나을 수도 있다.

그런 걸 고려해서.. 투 포인터로 바꾸고, 리스트 생성도 하지 않고, 그냥 숫자나 알파벳이 아닌 경우 포인터를 옮기는 방식으로 개선하면 이렇게도 할 수 있다.

 

class Solution {
    private boolean isValid(char c) {
        return Character.isLetterOrDigit(c);
    }

    private char normalize(char c) {
        return Character.toLowerCase(c);
    }
    
    public boolean isPalindrome(String s) {
        int left = 0;
        int right = s.length() - 1;

        while (left < right) {
            char l = s.charAt(left);
            char r = s.charAt(right);

            if (!isValid(l)) {
                left++;
                continue;
            }
            if (!isValid(r)) {
                right--;
                continue;
            }

            if (normalize(l) != normalize(r)) {
                return false;
            }

            left++;
            right--;
        }

        return true;
    }
}