[Java] leetcode 125. Valid Palindrome

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

1. 아이디어

많이 풀어본 팰린드롬 문제..
자바는 어떻게 푸는 것이 효율적일까?

• 풀이1. 문자 단위로 추출하여 양쪽에서 비교하며 좁히는 방식
• 풀이2. 문자열 자체를 복사하고 뒤집어서 비교

풀이1. 문자 단위로 추출 (String.chatAt(idx) 메서드를 이용)

문자 단위로 추출하여 양쪽에서 비교하며 좁히는 방식을 이용

자바에서는 원시형에 거의 1:1 대응하는 참조형을 지원하는데,
다양한 메서드를 지원하는 참조형은 사용하기엔 편리하지만 원시형에 비해 메모리를 많이 차지하고, 시간이 오래 걸린다.

문자 단위로 추출하는 방식을 사용하면 원시형인 char 를 이용하기 때문에 실행 속도가 매우 빠르다.

charAt(idx)

char 형으로 문자를 반환하는 String 클래스가 지원하는 chatAt(인덱스)를 이용하면
문자열로부터 쉽게 문자를 얻을 수 있다.

Character.toLowerCase()

말 그대로 문자를 소문자로 바꿔주는 유용한 녀석이다.
toUpperCase()도 있다.

Character.toLetterOrDigit()

해당 문제에서는 영문자와 숫자만을 비교의 대상으로 삼는다고 제한했다.
착한 Character 래퍼 클래스는 영숫자인지 boolean으로 알려주는 메서드를 제공해준다.

풀이1의 최종 코드

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

    while (start < end) {
    // 영숫자가 아니면 한 칸씩 패스
      if (!Character.isLetterOrDigit(s.charAt(start))) {
        start++;
      } else if (!Character.isLetterOrDigit(s.charAt(end))) {
        end--;
      } else {
      // 영숫자인 경우 start, end 위치의 문자를 비교해서 다르면 바로 false 반환
        if (Character.toLowerCase(s.charAt(start)) != Character.toLowerCase(s.charAt(end))) {
          return false;
        }
        // 통과했다면 그 다음을 비교할 수 있도록 포인터 이동
        start++;
        end--;
      }

    }
    return true;
  }
}

풀이2. 문자열 뒤집어서 비교

문자열을 뒤집어서 비교하는 단순한 방법도 있다.

String.replaceAll(정규식, 교체할_문자)

문자열의 형은 유지하면서 영숫자를 걸러주기 위해서 정규식을 이용하는 replaceAll()메서드를 이용할 수 있다.

'영숫자 아니고 모두' 라는 정규식 = "[^A-Za-z0-9]"

StringBuilder.reverse()

문자열을 뒤집는 메서드를 제공하는 StringBuilder 클래스를 이용해보자.

• 책에서 StringBuilder가 스레드 안전(Thread Safe)하지 않다고 이야기 했다.
  • Tread safe : 하나의 함수가 한 스레드로부터 호출되어 실행 중일 때, 다른 스레드가 그 함수를 호출하여 동시에 함께 실행되더라도 각 스레드에서의 함수의 수행 결과가 올바르게 나올 수 있음. (출처 : https://developer-ellen.tistory.com/205 )

풀이2의 최종 코드

public boolean isPalindrome(String s) {
    String s_filtered = s.replaceAll("[^A-Za-z0-9]", "").toLowerCase();
    String s_reversed = new StringBuilder(s_filtered).reverse().toString();
    return s_filtered == s_reversed;
}