[LeetCode] 125. Valid Palindrome - Java

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.

 

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.

---

풀이

풀이 과정

주어진 문자열에서 영문자와 숫자를 제외한 나머지 문자를 제외하고 소문자로 치환한 값이 Palindrome인지 판단하는 문제이다.

Palindrome이란 "다시 합창합시다", "Was it a cat i saw?" 와 같이 제대로 읽어도 거꾸로 읽어도 똑같은 단어나 구절을 의미한다.

먼저 주어진 문자열에서 정규식을 이용하여 알파벳과 숫자를 제외한 문자를 ""로 치환하고 소문자로 변환한다.

// 알파벳과 숫자를 제외한 문자를 ""으로 치환하고 소문자로 변환
s = s.replaceAll("[^a-zA-Z0-9]", "").toLowerCase();

 

그 후 양끝에서 부터 안쪽으로 이동하며 문자를 비교하여 두 문자가 다르다면 거꾸로 했을 때 다른 문자이므로 Palindrome이 아님을 알 수 있다.

// 반을 나누어 양쪽 끝부터 탐색
for(int i = 0; i < s.length() / 2; i++) {
    // 왼쪽 인덱스 : 문자열의 처음부터 시작
    int left = i;
    // 오른쪽 인덱스 : 문자열의 끝부터 시작
    int right = s.length() - 1 - i;

    // 왼쪽 문자와 오른쪽 문자가 다르다면 false를 return
    if(s.charAt(left) != s.charAt(right)) {
        return false;
    } 
}

return true;

---

최종 코드

class Solution {
    public boolean isPalindrome(String s) {
        // 알파벳과 숫자를 제외한 문자를 ""으로 치환하고 소문자로 변환
        s = s.replaceAll("[^a-zA-Z0-9]", "").toLowerCase();
        
        // 반을 나누어 양쪽 끝부터 탐색
        for(int i = 0; i < s.length() / 2; i++) {
            // 왼쪽 인덱스 : 문자열의 처음부터 시작
            int left = i;
            // 오른쪽 인덱스 : 문자열의 끝부터 시작
            int right = s.length() - 1 - i;
            
            // 왼쪽 문자와 오른쪽 문자가 다르다면 false를 return
            if(s.charAt(left) != s.charAt(right)) {
                return false;
            } 
        }
        return true;
    }
}

---