[LeetCode] 125. Valid Palindrome - Java

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이면 true, 아니면 false를 반환한다.

 

---

 

내 풀이

 

첫 번째 풀이

class Solution {
    public boolean isPalindrome(String s) {
        s = s.toLowerCase().replaceAll("[^a-z0-9]", "");

        int start = 0;
        int end = s.length() - 1;

        while(start <= end){
            if(s.charAt(start++) != s.charAt(end--)) return false;
        }

        return true;
    }
}

 

투 포인터를 사용해서 문제를 해결했다.

우선, String 내장 메서드와 정규식 연산을 통해 문자열을 조건에 맞게 변환해준다.

그 후 투 포인터를 사용하여 문자열 양 끝에서부터 한 글자씩 비교해주며 값이 다를경우 false를 반환한다.

 

• 시간복잡도 : O(n) + O(n) = O(n)
• 공간복잡도 : O(1)

 

실제 소요시간은 아래와 같다.

 

---

 

다른 사람의 풀이

시간을 줄일 수 있는 방법이 있을지 궁금하여 다른 사람들의 풀이를 찾아보았다.

class Solution {
    public boolean isPalindrome(String s) {
        int start = 0;
        int end = s.length() - 1;

        while (start < end) {
            char c1 = s.charAt(start);
            char c2 = s.charAt(end);

            if (!isAlphanumeric(c1)) {
                start++;
            } else if (!isAlphanumeric(c2)) {
                end--;
            } else {
                if (Character.toLowerCase(c1) != Character.toLowerCase(c2)) {
                    return false;
                }
                start++;
                end--;
            }
        }

        return true;
    }

    private boolean isAlphanumeric(char c) {
        return Character.isLetter(c) || Character.isDigit(c);
    }
}

처음에 문자열을 변환하지 않고, 투 포인터를 사용하여 순회를 하다가 조건에 맞지 않는 문자(공백이나, 영숫자가 아닌 문자)를 만나면 해당 문자는 무시하고 포인터를 이동하는 방식으로 푸는 방식이다.

처음에 정규식 연산을 통해 문자열을 한 번 스캔하는 과정을 거치지 않다보니 실제 소요 시간이 훨씬 줄어든다.

단순화하지 않은 시간복잡도로 나타내면 O(2n)에서 O(n)으로 줄어드는 것이다.

 

Character 의 isLetter() 나 isDigit() 과 같은 내장메서드들을 처음 알게되었다.

해당 문자가 숫자인지 문자인지 간단한 판별이 필요할 때 유용하게 사용할 수 있을 것 같다.

 

실제 소요 시간은 아래와 같다.

 

 

하지만, 코드 가독성도 고려해야하기 때문에 난 굳이 이렇게 짜진 않을 것 같다.

물론 문자열의 크기가 커질수록 상대적으로 더 빠를 수 있지만 유의미한 차이는 아니라고 생각한다.