[LeetCode] 125. Valid Palindrome

125. Valid Palindrome

LeetCode

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

Valid Palindrome - LeetCode

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.

모든 대문자를 소문자로 변환하고 영숫자(알파벳과 숫자)가 아닌 문자를 모두 제거했을 때, 앞으로 읽으나 뒤로 읽으나 똑같다면 그 구문은 팰린드롬(회문)입니다. 영숫자에는 영문자와 숫자가 포함됩니다. 문자열 s가 주어졌을 때, 팰린드롬이면 true를 반환하고 그렇지 않으면 false를 반환하세요.

 

Example

Input: s = "A man, a plan, a canal: Panama"
Output: true
Explanation: "amanaplanacanalpanama" is a palindrome.

Input: s = "race a car"
Output: false
Explanation: "raceacar" is not a palindrome.

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.

---

1. 문제 요구사항 분석

영숫자를 제외한 문자를 제거한 후, 왼쪽과 오른쪽 문자가 동일한지 비교하는 문제

2. 접근 전략

😭 정규식을 이용한 문자 제거 및 양옆 비교

- 시간 복잡도 : O(N) / 공간 복잡도 : O(N)

정규식과 toLowerCase 공간을 많이 차지함...! 원본 문자열 길이에 비례하는 새로운 String 객체가 메모리에 할당됨 !!!!!!

class Solution {
    public boolean isPalindrome(String s) {
        String st = s.replaceAll("[^a-zA-Z0-9]", ""); // 문자 바꾸기
        if (st.length() == 0) return true;
        st = st.toLowerCase(); // 소문자로 치환
        
        // 양옆 비교
        for (int i = 0; i < st.length() / 2; i++) {
            if (st.charAt(i) != st.charAt(st.length() - 1 - i)) {
                return false;
            }
        }
        
        return true;
    }
}

 

😁 투 포인터와 아스키코드 이용

- 시간 복잡도 : O(N) / 공간 복잡도 : O(1)

class Solution {
    public boolean isPalindrome(String s) {
        int left = 0, right = s.length()-1;
        char ch1 = '0';
        char ch2 = '0';
        while(left < right) {
            ch1 = s.charAt(left);
            ch2 = s.charAt(right);
            if(ch1 >= 'A' && ch1 <= 'Z') {
                ch1 = (char) (ch1 + 32);
            }
            if(ch2 >= 'A' && ch2 <= 'Z') {
                ch2 = (char) (ch2 + 32);
            }
            if(!((ch1 >= 'a' && ch1 <= 'z') || (ch1 >= '0' && ch1 <= '9'))) {
                left++;
                continue;
            }
            if(!((ch2 >= 'a' && ch2 <= 'z') || (ch2 >= '0' && ch2 <= '9'))) {
                right--;
                continue;
            }
            if(ch1 != ch2) {
                return false;
            }
            left++;
            right--;
        }
        return true;
    }
}