LeetCode 125 Valid Palindrome

nayu1105·2023년 8월 26일

leetcode 알고리즘

LeetCode

목록 보기

10/28

LeetCode 125 Valid Palindrome 풀러가기

문제

문자열이 주어졌을 때 palindrome인지 확인하는 함수를 구해라.

palindrome이란 문자열에 있는 문자 중 영어와 숫자 외의 모든 문자 제외, 공백 제외한 후 영어를 소문자로 모두 했을 때 앞에서 읽어도, 뒤에서 읽어도 같은 문자열이다.

예를 들어, "A man, a plan, a canal: Panama"은 "amanaplanacanalpanama" 으로 팰린드롬이 맞고,

"race a car" 은 "raceacar" 로 중간에 e와 a가 달라 팰린드롬이 아니다.

" " 은 공백을 제외하면 앞에서 읽어도, 뒤에서 읽어도 같은 문자열이기에 팰린드롬이 맞다.

문제 분석

첫번째 시도

먼저 팰린드롬 검사를 하기 위해서는 공백 제거, 특수문자 제거를 해야 한다.

이를 위해 문자열에 공백과 특수문자 제거를 위해 String.replace하고, 팰린드롬 검사를 다시한다면 문자열 길이가 최대 2 * 10^5 이라 시간이 오래 걸릴 것 같았다.

그래서 start, end 의 index 두 개를 놓고, 숫자 또는 영문자가 나올때까지 증가 혹은 감소하며 비교하는 코드를 짰다.

이렇게 되면 최대 N번 검사를 한다.

영문자는 소문자로 통일하기 위해 Character의 toLowerCase 함수를 사용하고, 숫자 혹은 영어 소문자인지 확인하기 위해 character의 아스키값 인자를 받는 valid함수를 만들어 사용했다.

코드

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

        while (start < end) {
            while (start <= end && !valid(Character.toLowerCase(s.charAt(start)))) {
                start++;
            }

            while (start <= end && !valid(Character.toLowerCase(s.charAt(end)))) {
                end--;
            }

            if (start > end)
                return true;

            if (start == end) {
                if (Character.toLowerCase(s.charAt(start)) == Character.toLowerCase(s.charAt(end)))
                    return true;
                else
                    return false;
            }

            if (Character.toLowerCase(s.charAt(start)) == Character.toLowerCase(s.charAt(end))) {
                start++;
                end--;
            } else
                return false;

        }

        return true;
    }

    static boolean valid(int n) {
        return (n >= 48 && n <= 57) || (n >= 97 && n <= 122);
    }
}

결과 : 성공

Runtime

Memory

시간은 굉장히 짧았지만, 메모리 부분이 조금 아쉬웠다. if 연산을 많이 하고, toLowerCase 함수를 많이써서 인듯하다.

두번쨰 시도 (메모리 감소)

이번에는 메모리를 줄이기 위해 while 문 을 조금 바꾸어 보았다.

안에 있는 return true 구문은 어짜피 while 문을 벗어나면 true값을 반환해주기 때문에 삭제하였다.
start와 end 값이 같을 때도 비교후, 같다면 start++, end--를 하며 start 가 end보다 커지기 때문에 while 문을 벗어나며 true를 반환한다. 그래서 이 조건도 삭제하였다.
숫자 혹은 문자 인지 판단하기 위해 valid라는 함수를 사용했는데, Character에서 isLetterOrDigit 라고, 문자혹은숫자인지 판단해주는 함수가 있었다. 반환값은 true/false이다. 그래서 valid함수를 없애고, 이를 이용했다.
isLetterOrDigit 참고

코드

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

        while (start <= end) {
            while (start < end && !Character.isLetterOrDigit(s.charAt(start))) {
                start++;
            }

            while (start < end && !Character.isLetterOrDigit(s.charAt(end))) {
                end--;
            }

            if (Character.toLowerCase(s.charAt(start)) == Character.toLowerCase(s.charAt(end))) {
                start++;
                end--;
            } else
                return false;

        }

        return true;
    }
}