[leetcode - Java] 125. Valid Palindrome

1. 문제

---

• 입력받은 문자열을 소문자로 변환, 특수문자를 제거하고 뒤집었을 때 내용이 똑같게 만들어라. 문자열을 뒤집었을 때 스펠링 순서가 다르면 실패

2. 의사 코드

---

1. 문자열 소문자 변환 & 특수문자, 공백 제거
str = str.replaceAll("[제거할 특수문자들]").toLowerCase();

2-1 문자열 뒤집어 true/false 판단 
2-2 투 포인터를 사용해 문자열 양 끝(left, right)에서부터 비교하며 양 끝의 문자가 같다면 left++ right--, 아니면 false

3. 시도

---

3-1. 문자열s 뒤집기

class Solution {
    public boolean isPalindrome(String s) {
        s = s.replaceAll("[^a-zA-Z0-9]", "").toLowerCase();
        String reverse = "";

        for (int i = s.length() - 1; i >= 0; i--) {
            reverse += s.charAt(i);
        }
        if (!reverse.equals(s)) {
            return false;
        }

        return true;
    }
}

1. 문자열 s를 반복문을 통해 뒤에서부터 빈 문자열 reverse에 담았다.
2. 반복문이 끝나고 문자열 s와 문자열s가 거꾸로 담긴 reverse 문자열을 통째로 비교한다. 

3-2. 투 포인터 활용

class Solution {
    public boolean isPalindrome(String s) {
        s = s.replaceAll("[^a-zA-Z0-9]", "").toLowerCase();
        int left = 0;
        int right = s.length()-1;

        while (left < right) {
            if (s.charAt(left) != s.charAt(right)) {
                return false;
            }
            left++;
            right--;
        }

        return true;
    }
}

1. 문자열의 시작 인덱스와 끝 인덱스를 설정한다.
2. 문자열 s의 양 끝 문자를 비교하고 일치하면 하나씩 줄이며 나머지 문자 비교
3. 일치하지 않으면 false 반환

4. 개선

---

시간 복잡도는 알고리즘이 문제를 해결하는데 걸린 시간을 나타낸다고 한다. 일반적으로 Big O 표기법을 따르는데, 아직 제대로 구하는 방법은 모르지만 내가 작성한 코드의 시간 복잡도는 어떤지 궁금했다.

내가 작성한 두 가지 표기법의 시간 복잡도는 아래와 같다.

문자열s 뒤집기

1. 문자열 s에 대해 replaceAll을 하는데 O(n)
2. 문자열 s에 대해 toLowerCase를 하는데 O(n)
3. 문자열 길이(s.length-1) 만큼 반복하기에 일반적으로 O(n)이라고 한다. 하지만 나의 경우, 불변인 String을 사용하여 reverse에 += 연산으로 매번 새로운 문자열 객체를 생성해 O(n^2)이라고 한다.
4. if (!reverse.equals(s)) 이 코드에서 최대 문자열s의 길이만큼 equals가 실행될 수 있기에 O(n)이고, 최종적으로 가장 큰 O(n^2)이 나오게 된다.
   

투 포인터 활용

1. 문자열 s에 대해 replaceAll을 하는데 O(n)
2. 문자열 s에 대해 toLowerCase를 하는데 O(n)
3. while 반복문에서 left와 right가 동시에 가운데 인덱스로 이동하기에 (문자열s 길이 / 2) = (O(n/2))이다. 그러나 빅 오 표기법에서 상수는 무시되기에 O(n)가 적용되고 최종적으로 O(3n) -> O(n)이 된다.
   

두 가지 방법을 비교했을 때 첫 번째로 적용한 문자열s 뒤집기는 개선의 여지가 있다. 아래는 불변 문자열 String reverse를 가변인 Builder로 변경하여 사용한 예시이다.

class Solution {
    public boolean isPalindrome(String s) {
        s = s.replaceAll("[^a-zA-Z0-9]", "").toLowerCase();
        StringBuilder reverse = new StringBuilder();

        for (int i = s.length() - 1; i >= 0; i--) {
            reverse.append(s.charAt(i));
        }
        if (!reverse.toString().equals(s)) {
            return false;
        }

        return true;
    }
}