[ Top Interview 150 ] 125. Valid Palindrome

문제

125. Valid Palindrome

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.

• Input : 여러가지 문자가 섞여있는 문자열 s
• Output : 문자열이 앞뒤 대칭인지 여부
  • 대칭 여부를 판단할 때, 영어/숫자 외 문자는 무시할 것
  • 대칭 여부를 판단할 때, 영어 대문자는 모두 소문자로 간주할 것

알고리즘 전략

1. 문자열 다듬기 (문자열을 순회하면서 조건에 따라 새로운 String 만들기)
   • 영어/숫자 문자만을 넣을 것
   • 대문자는 전부 소문자로 바꿀 것
2. Palindrome 확인하기
   • 문자열을 순회하면서, i번째 문자와 n - 1 - i번째 문자가 같은지 확인 (n : 다듬어진 문자열 길이)

답안

1차 답안

• 알고리즘 전략 반영
  • Time complexity : O(n)
  • Space complexity: O(n)

class Solution {
    public boolean isPalindrome(String s) {
        StringBuilder sb = new StringBuilder();
        for (char ch : s.toLowerCase().toCharArray()) {
            if (('a' <= ch && ch <= 'z' || '0' <= ch && ch <= '9')) {
                sb.append(ch);
            }
        }
        
        char[] palindrome = sb.toString().toCharArray();
        for (int i = 0; i < palindrome.length / 2; i++) {
            if (palindrome[i] != palindrome[palindrome.length - 1 - i]) {
                return false;
            }
        }
        return true;
    }
}

1차 답안 개선 방안

• s.toLowerCase(), string.toCharArray(), StringBuilder 을 통해 중간중간에 생성하는 String 객체가 꽤 많다.
• 이를 double pointer 방법을 이용하여 조건에 일치할때만을 비교한다면, Space complexity를 O(1)으로 만들 수 있다.

2차 답안

• double pointer 방법을 이용

  • 두 조건이 특정 조건과 일치할 때 알 뒤 두 문자를 비교한다.
  • 특정 조건과 일치하지 않은 경우, 다음으로 넘어간다.

• complexity

  • Time complexity : O(n)
  • Space complexity: O(1)

• 개선 사항

  • 추가적인 String 객체 생성을 하지 않아 시간과 메모리 사용량이 줄어듦

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

        while(front < behind) {
            if (!isAlphanumeric(s.charAt(front))) {
                front++;
                continue;
            } 
            
            if (!isAlphanumeric(s.charAt(behind))) {
                behind--;
                continue;
            }

            if (!isSameLetter(s.charAt(front), s.charAt(behind))) {
                return false;
            }
            front++;
            behind--;
        }

        return true;
    }

    private boolean isAlphanumeric(char letter) {
        return 'A' <= letter && letter <= 'Z' 
            || 'a' <= letter && letter <= 'z'
            || '0' <= letter && letter <= '9';
    }

    private boolean isSameLetter(char letter1, char letter2) {
        if ('0' <= letter1 && letter1 <= '9') {
            return letter1 == letter2;
        }

        return letter1 == letter2 
            || letter1 - letter2 == 'A' - 'a'
            || letter1 - letter2 == 'a' - 'A';
    }
}