문제

Valid Palindrome - LeetCode

Code

내 풀이

class Solution {
    public boolean isPalindrome(String s) {
        String afterString = removeAllNonAlphaNumeric(s);

        int halfOfStringLength = afterString.length() / 2;

        for (int i = 0; i < halfOfStringLength; i ++){
            if (afterString.charAt(i) != afterString.charAt(afterString.length() - i - 1)){
                return false;
            }
        }
        return true;
    }

    private String removeAllNonAlphaNumeric(String s){
        if (s == null){
            return "";
        } else {
            return s.toUpperCase().replaceAll("[^A-Za-z0-9]", "");
        }
    }
}

1. Regex, replaceAll을 이용하여 숫자, 알파벳을 제외한 문자들을 제외하였다.
2. 앞에서부터 매칭되는 뒷 문자와 비교하였다.

해설

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

        while (start < end){
            System.out.println("start = " + s.charAt(start) + " end = " + s.charAt(end));
            if (!Character.isLetterOrDigit(s.charAt(start))){
                start ++;
            } else if (!Character.isLetterOrDigit(s.charAt(end))){
                end --;
            } else{
                if (Character.toUpperCase(s.charAt(start)) != Character.toUpperCase(s.charAt(end))){
                    return false;
                }
                start ++;
                end --;
            }
        }
        return true;
    }
}

1. 앞 뒤에서 각각의 포인터를 설정.
2. 알파벳이나 숫자가 아닌 경우 패스하면서 비교한다.
3. Regex를 사용하지 않고 바로 탐색해서 그런가 엄청 빠르다.

다른 풀이

import java.util.regex.Matcher;
import java.util.regex.Pattern;

class Solution {
    private static final Pattern REGEX_PATTERN = Pattern.compile("[^A-Za-z0-9]");

    public boolean isPalindrome(String s) {
        String afterString = removeAllNonAlphaNumeric(s);
        int halfOfStringLength = afterString.length() / 2;

        for (int i = 0; i < halfOfStringLength; i ++){
	                return false;
            }
        }
        return true;
    }

    private static String removeAllNonAlphaNumeric(String s){
        if (s == null){
            return "";
        } else {
            Matcher matcher = REGEX_PATTERN.matcher(s);
            return matcher.replaceAll("");
        }
    }
}

• Java에서 Pattern, Matcher를 사용하여 Regex를 사용하는 것이 성능이 더 좋다고 해서 사용해보았다.
  • 반복적으로 Regex를 사용할 때 Precompile을 함으로써 성능을 개선할 수 있다고 한다.
• 이 경우에는 Pattern REGEX_PATTERN이 상수로 선언되었기에 여러 테스트케이스에서 반복적으로 사용되면서 성능이 향상된 것으로 생각된다.

Reference

https://velog.io/@byeongju/%EC%A0%95%EA%B7%9C%ED%91%9C%ED%98%84%EC%8B%9D%EC%9D%84-%EA%B2%80%EC%82%AC%EB%A5%BC-%EB%8D%94-%ED%9A%A8%EC%9C%A8%EC%A0%81%EC%9C%BC%EB%A1%9C-%ED%95%B4%EB%B3%B4%EC%9E%90