팰린드롬

팰린드롬은 순서를 거꾸로 읽었을 때도 원래의 문자열이나 수열과 동일한 경우

 

1. 투포인터 방식

public static boolean isPalindrome(String str) {
    int left = 0;
    int right = str.length() - 1;

    while (left < right) {
        // 대소문자 무시하고 비교하고 싶다면: toLowerCase() 사용
        if (str.charAt(left) != str.charAt(right)) {
            return false;
        }
        left++;
        right--;
    }
    return true;
}

 

2. 문자열을 뒤집는 방식

public static boolean isPalindrome(String str) {
    String reversed = new StringBuilder(str).reverse().toString();
    return str.equals(reversed);
}

 

시간복잡도는 모두 O(N)으로 동일하지만

투포인터는 N/2이고, 문자열을 뒤집는 경우 2N이고 문자열 뒤집기는 새로운 문자를 만드는 추가적인 공간 N을 필요로 한다.