[C/LeetCode] Valid PalindromeⅡ

Daily LeetCoding Challenge April, Day 2

 

문제: Palindrome 가능 여부 확인

이때 최대 1개의 글자를 삭제 가능하다.

 

아이디어: Brute Force

 

문자를 제거할 수 있다는 것은 앞에서 비교할 때는 index+1, 뒤에서 비교할때는 index-1 하는 것이므로

두가지의 가능성이 있다. 따라서 둘 중에 하나가 true라면 palindrome인 것이다.

 

완성

submission: 44ms / 9.1MB

 

bool checkValid(char *s, int start, int end)
{
    while (start < end)
    {
        if (s[start] != s[end])
            return false;
        start++;
        end--;
    }
    return true;
}

bool validPalindrome(char *s){
    int start = 0;
    int end = 0;
    while (s[end] != 0)
        end++;
    
    end--;
    while (start < end)
    {
        if (s[start] == s[end])
        {
            start++;
            end--;
        }
        else
        {
            return checkValid(s, start + 1, end) || checkValid(s, start, end - 1);
        }
    }
    return true;

}