Leetcode - 125. Valid Palindrome - Easy

오늘의 문제는 Palindrome인지 여부를 알아보는 건데요. 입력값에서 스페이스와 부호들을 다 빼고 모든 글자를 소문자로 바꾼 후 체크해야 합니다.

 

제가 만든 코드는 아래와 같습니다.

 

-

- 입력값에서 모든 스페이스를 제거 한다.  -> line 4

- 입력값에서 모든 부호를 제거한다. -> line 5

- 입력값에서 모든 대문자를 소문자로 바꾼다. -> line 6

 

그 다음에 StringBuilder의 reverse를 사용해서 그 값을 reverse합니다. -> line 8

그리고 String의 equals()를 사용해서 두 값을 비교합니다.

 

아주 간단하게 처리했습니다.

Runtime과 Memory는 아래와 같습니다.

Approach 2

 

아래 코드는 비슷한 로직인데 제가 한 것 처럼 정규직을 쓰지 않고 다른 내부 함수를 사용해서 코딩한 것입니다.

 

class Solution {
  public boolean isPalindrome(String s) {
    StringBuilder builder = new StringBuilder();

    for (char ch : s.toCharArray()) {
      if (Character.isLetterOrDigit(ch)) {
        builder.append(Character.toLowerCase(ch));
      }
    }

    String filteredString = builder.toString();
    String reversedString = builder.reverse().toString();

    return filteredString.equals(reversedString);
  }

  /** An alternate solution using Java 8 Streams */
  public boolean isPalindromeUsingStreams(String s) {
    StringBuilder builder = new StringBuilder();

    s.chars()
        .filter(c -> Character.isLetterOrDigit(c))
        .mapToObj(c -> Character.toLowerCase((char) c))
        .forEach(builder::append);

    return builder.toString().equals(builder.reverse().toString());
  }
}

 

위에 3개가 이 코드로 돌린 건데요.

제가 만든 코드로 돌린 것 보다 Runtime이 확실히 줄어 드네요. 메모리도 약간 줄어 들고요.

이 코드를 좀 공부 해 둬야 겠습니다.

 

Approach 3

 

 

다음은 입력문의 첫번째와 마지막 글자부터 비교하는 것입니다.

중간에 스페이스나 부호들은 건너 뜁니다.

그러니까 그것들을 remove하는 것을 하지 않아도 됩니다.

 

class Solution {
  public boolean isPalindrome(String s) {
    for (int i = 0, j = s.length() - 1; i < j; i++, j--) {
      while (i < j && !Character.isLetterOrDigit(s.charAt(i))) {
        i++;
      }
      while (i < j && !Character.isLetterOrDigit(s.charAt(j))) {
        j--;
      }

      if (Character.toLowerCase(s.charAt(i)) != Character.toLowerCase(s.charAt(j)))
        return false;
    }

    return true;
  }
}

 

마지막 방법이 훨씬 Performance가 좋네요.

 

내가 생각했던 쉽게 접근 하는 방법에서 조금만 더 머리를 쓴 건데 훨씬 좋은 performances 를 보이는 군요.

잘 배워 둬야 겠습니다.