[LeetCode/Top Interview 150] [Two Pointers] 125. Valid Palindrome

문제 링크: https://leetcode.com/problems/valid-palindrome/?envType=study-plan-v2&envId=top-interview-150
사용 언어: Java(OpenJDK 17. Java 8)

난이도: easy

문제:

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.

전략:

먼저 주어진 문자열을 toLowerCase와 trim, charAt을 이용해 알파벳 소문자와 숫자로만 이루어진 문자열로 바꾼다.
회문인지 아닌지 판별하기 위해서는 시작과 끝 양 끝단의 포인터를 비교하다가 같지 않은게 나오는 순간 false, 두 포인터가 한 점에서 만날 때 까지 false가 안 난다면 true

코드 구현:

class Solution {
    public boolean isPalindrome(String s) {
        // 문자만 남기기
        s = trim(s);
        
        // 빈 문자열인 경우 true
        if (s.length() == 0) {
            return true;
        }
        
        // 투포인터로 비교후 다른 경우 즉시 false 리턴
        for (int i=0;i<s.length()/2;i++) {
            if (s.charAt(i) != s.charAt(s.length()-1-i)) {
               return false; 
            }
        }
        // 투포인터 통과시 회문
        return true;
    }
    
    public String trim(String s) {
        s=s.toLowerCase();
        StringBuilder sb = new StringBuilder();
        for (int i=0;i<s.length();i++) {            
            char c = s.charAt(i);
            // 숫자 또는 알파벳 소문자만
            if ((c >= '0' && c <= '9') || (c >= 'a' && c <= 'z')) {
                sb.append(c);
            }
        }
        return sb.toString();
    }
}

실행결과:
Time: 3 ms (87.05%), Space: 43.5 MB (59.15%) - LeetHub
https://github.com/1-vL/LeetCode/blob/main/0125-valid-palindrome/0125-valid-palindrome.java

개선 방안:

java String에서 alphanumeric한 글자만 남기는 기본 메서드가 분명 있을거 같은데 모르겠어서 냅다 만들어서 푼 부분에서 복잡도가 증가하지 않았나 싶다.
StringBuilder로 문자열로 바꾸는게 아니라 바로 char인 상태로 비교하고, 실패시에는 다시 이전에 비교한 문자를 비교하는 식으로 하면 더 빠를듯하다.

Discuss 탭의 타인 코드:

class Solution{
public  boolean isPalindrome(String s) {
        // int i = 0, j = s.length() - 1;
        // 0 9  A Z  a z
        
        char[] c = s.toCharArray();
        int i = 0, j = c.length - 1;
        // if(c.length==2){
        //     return c[i]==c[j]?true:false;
        // }
        while (i <=j) {
            if (upper(c[i])) {
                c[i] = tolowercase(c[i]);
            }
            if (upper(c[j])) {
                c[j] = tolowercase(c[j]);
            }
            i++;
            j--;
        }
        // 2 -1
        // System.out.println(Arrays.toString(c));
        i = 0;
        j = c.length - 1;
        while (i < j) {
            while (i<c.length&&!isalphanu(c[i])) {
                i++;
            }
            while (i<c.length&&!isalphanu(c[j])) {
                j--;
            }
            if(j<i){
                return true;
            }
            if (c[i] != c[j]) {
                return false;
            }
            i++;
            j--;
        }
        return true;
    }

    public  char tolowercase(char c) {
        return (char) (c + 32);
    }

    public  boolean isalphanu(char c) {
        boolean b = (c >= '0' && c <= '9') || (c >= 'a' && c <= 'z') ? true : false;
        return b;
    }

    public  boolean upper(char c) {
        return (c >= 'A' && c <= 'Z') ? true : false;
    }
}
Time: 2 ms (99.64%), Space: 42.1 MB (73.32%) - LeetHub

회고:

While문을 돌면서 char 배열을 순회하는 부분에서 성능차이가 난 것 같다. 내 코드도 한 번 그 부분을 직접 구현해 봐야겠다. 그래도 역시 처음에 한 번 문자열을 깔끔하게 정리하는 과정은 생략할 수 없는 듯 하다.

class Solution {
    public boolean isPalindrome(String s) {
        // char 배열 가져오기
        char[] array = s.toCharArray();
        
        // 앞 포인터 i, 뒤 포인터 j
        int i = 0;
        int j = s.length()-1;
        
        // char 배열 정리
        while (i <=j) {
            if (isUpper(array[i])) {
                array[i] = toLowerCase(array[i]);
            }
            if (isUpper(array[j])) {
                array[j] = toLowerCase(array[j]);
            }
            i++;
            j--;
        }
        
        i = 0;
        j = s.length()-1;
        // 두 포인터가 만나면 탈출
        
        while (i < j) {
            while (i<array.length&&!isAlphaNumeric(array[i])) {
                i++;
            }
            while (i<array.length&&!isAlphaNumeric(array[j])) {
                j--;
            }
            if(j<i){
                return true;
            }
            if (array[i] != array[j]) {
                return false;
            }
            i++;
            j--;
        }
        return true;
    }
    
    public boolean isAlphaNumeric(char c) {
        // 숫자 또는 알파벳 소문자만
        if ((c >= '0' && c <= '9') || (c >= 'a' && c <= 'z')) {
            return true;
        }
        return false;
    }
    
    public char toLowerCase(char c) {
        return (char) (c+32);
    }
    public boolean isUpper(char c) {        
        if (c >= 'A' && c <= 'Z') {
            return true;
        }
        return false;
    }
}
Time: 2 ms (99.64%), Space: 41.8 MB (90.71%) - LeetHub