[HackerRank] Palindrome Index

문제

문자열 s 의 특정 문자 하나를 지워 회문(palindrome)이 된다면 그 문자의 인덱스를 반환하는 함수 palindromeIndex 를 완성하라.

s 가 이미 회문이거나 회문을 만들 수 없는 경우 -1 을 반환하라.

회문이란?
그대로 읽을 때, 거꾸로 읽을 때 모두 같은 단어로 읽히는 단어.
예를 들면 "호불호", "madam", ...

답안

bool is_palindrome(const string& s, int left, int right) {
    while (left < right) {
        if (s[left] != s[right]) return false;
        ++left;
        --right;
    }
    return true;
}

int palindromeIndex(const string& s) {
    int head = 0, tail = s.size() - 1;
    
    while (head < tail) {
        if (s[head] != s[tail]) {
            // 앞쪽 문자 제거 시 palindrome 여부 확인
            if (is_palindrome(s, head + 1, tail)) return head;
            // 뒷쪽 문자 제거 시 palindrome 여부 확인
            if (is_palindrome(s, head, tail - 1)) return tail;
            return -1; // 어느 한쪽을 제거해도 palindrome이 되지 않음
        }
        ++head;
        --tail;
    }
    
    return -1; // 이미 palindrome인 경우
}

시간 복잡도

is_palindrome 함수 : $O(N)$

palindromeIndex 함수 : $O(N)$