[알고리즘] LeetCode - Valid Palindrome

Valid Palindrome - LeetCode

문제 설명

• 문자열 s가 주어진다.
• 문자열에 알파벳 소문자뿐만 아니라 대문자와 특수문자도 같이 포함된다.
• 문자열 s가 회문인지 아닌지 판별하여 결과를 반환한다.

문제 해결

• 대문자는 소문자로 변환하고, 특수문자는 제거한 문자열을 만든다.
• 두 개의 포인터(투포인터)를 이용해 양쪽에서 동시에 접근하여 회문인지 여부를 판단한다.
• StringBuilder를 이용해 문자열을 필터링하여 문자열 처리하는데 시간을 단축시킨다.

시간 복잡도

• O(N)
• 문자열 길이가 N일 때 (N + N / 2) 만큼 돌기 때문에 시간 복잡도는 O(N)이다.

유사코드

문자열 변수 str선언

문자열 길이 만큼 반복
    소문자인 경우
    	str에 저장
    숫자인 경우
    	str에 저장
    대문자인 경우
    	str에 소문자로 변환 후 저장

문자열 길이/2 만큼 반복(앞에서부터 올라가는 인덱스 : head, 뒤에서부터 내려오는 인덱스 : tail)
    if: str의 head번째 문자 값과 str의 tail번째 문자 값이 다르면
        return false
    head++
    tail--
return true

풀이 코드

import java.util.*;

class Solution {
    public boolean isPalindrome(String s) {
        StringBuilder str = new StringBuilder();
        
        int toLower = 'a'-'A';
        for (int i = 0; i < s.length(); i++) {
            char now = s.charAt(i);
            if ('a' <= now && now <= 'z') {
                str.append(now);
            } else if ('0' <= now && now <= '9') {
                str.append(now);
            } else if ('A' <= now && now <= 'Z') {
                str.append((char) (now + toLower));
            }
        }

        s = str.toString();
        int head = 0, tail = s.length() - 1;
        char[] arr = s.toCharArray();

        while(head <= tail) {
            if (arr[head] != arr[tail]) {
                return false;
            }
            head++;
            tail--;
        }

        return true;      
    }
}

결과

시간	메모리
2 ms	43.5 MB