Sword finger offer II 019 Delete at most one character to get a palindrome

Address ：

Power button https://leetcode-cn.com/problems/RQku0D/

This question is related to    680. Verify palindrome string Ⅱ  identical

subject ：

Given a non empty string  s, Please judge if   most If you delete a character from the string, you can get a palindrome string .

Example 1:

Input : s = "aba" Output : true

Example 2:

Input : s = "abca" Output : true explain : You can delete "c" character perhaps "b" character

Example 3:

Input : s = "abc" Output : false

Tips :

1 <= s.length <= 105 s It's made up of lowercase letters

source ： Power button （LeetCode）
link ：https://leetcode-cn.com/problems/RQku0D
Copyright belongs to the network . For commercial reprint, please contact the official authority , Non-commercial reprint please indicate the source .

Ideas ：

Here are some examples ：

Palindrome ：abba,abcba

         It can be seen that as long as palindromes are deleted 1 Times are still palindromes

Non palindrome ：abcb,bcba,cbbcc

        The left pointer points to [0], The right pointer points to [len-1], Adjust the left or right pointer once , If the rest is palindromes, then you can

        Let's take a longer example ：ebcbbececabbacecbbcbe

                The left pointer can be adjusted [5] ->[6], The right pointer cannot be adjusted [15]->[14], The total number of adjustments is also one

So the conclusion is , Scan the entire string with double pointers , If it's palindrome perhaps After one adjustment, the substring is also a palindrome , Then the result is ok , Otherwise, you can't

bool checksub(char *s, int i, int j)
{
    bool ret = true;

    while(i < j)
    {
        if(s[i] != s[j])
        {
            ret = false;
            break;
        }
        i++;
        j--;
    }

    return ret;
}

bool validPalindrome(char * s){
    int slen = strlen(s);
    int i,j;
    int maxjudge = 0;
    bool ret = true;

    i = 0;
    j = slen - 1;

    while(i < j)
    {
        if(s[i] != s[j])
        {
            if( checksub(s, i, j-1) || checksub(s, i+1, j) )
            {
                ret = true;
                break;
            }
            else
            {
                ret = false;
                break;
            }
        }

        i++;
        j--;
    }

    return ret;
}

See more brush notes