Difficulty: Easy

Given a non-empty string s, at most one character is deleted. Determines whether it can become a palindrome string.

Their thinking

Definition of two Pointers, pointing to the head and tail, if the encounter is not the same, there will be three cases, the first is to remove the low remaining palindrome string, the second is to remove the high remaining palindrome string, the third is not consistent.

Answer key

public boolean validPalindrome(String s) {
    int left = 0;
    int right = s.length() - 1;
    char leftChar, rightChar;
    while (left < right) {
        leftChar = s.charAt(left);
        rightChar = s.charAt(right);
        if(leftChar ! = rightChar) {return validPalindrome(s, left + 1, right) || validPalindrome(s, left, right - 1);
        }
        ++left;
        --right;
    }
    return true;
}

private boolean validPalindrome(String s, int left, int right) {
    while (left < right) {
        if (s.charAt(left) == s.charAt(right)) {
            ++left;
            --right;
        } else {
            return false; }}return true;
}
Copy the code

test

ValidPalindromeII validPalindromeII = new ValidPalindromeII();

@Test
public void test_case1(a) {
    Assertions.assertTrue(validPalindromeII.validPalindrome("aba"));
}

@Test
public void test_case2(a) {
    Assertions.assertTrue(validPalindromeII.validPalindrome("abca"));
}

@Test
public void test_case3(a) {
    Assertions.assertTrue(validPalindromeII.validPalindrome("abbda"));
}

@Test
public void test_case4(a) {
    Assertions.assertFalse(validPalindromeII.validPalindrome("abc"));
}

@Test
public void test_case5(a) {
    Assertions.assertTrue(validPalindromeII.validPalindrome("ebcbbececabbacecbbcbe"));
}
Copy the code