The topics are as follows:

Given a non empty string s, at most one character can be deleted. Determine whether it can be a palindrome string.

The topic requires that you specify a non empty string, delete at most one character, and judge whether it can be called palindrome string. First, you need to consider whether the given string is already palindrome string. If so, you can directly return true; If not, you need to delete a character to make it a palindrome string.

Since only one character is allowed to be deleted at most, it is easy to think of the violent exhaustive method. For a given string, delete it from left to right, judge whether the deleted string is a palindrome string, and return true if the conditions are met; If not, false is returned.

For example:

First, delete the character a, and the original string will become bca. At this time, judge whether bca is a palindrome string:

bca is not a palindrome string, so continue to delete the second character b. at this time, judge whether aca is a palindrome string:

aca is not a palindrome string, so continue to delete the third character c. at this time, judge whether aba is a palindrome string:

aba is a palindrome string. The program can end here and return true.

The resulting code is as follows:

public class Solution {

    public static boolean validPalindrome(String s) {
        // First, directly judge whether s is a palindrome string
        boolean flag = isPdStr(s);
        if (flag) {
            return true;
        }
        // If s itself is not a palindrome string, delete each character in turn
        for (int i = 0; i < s.length(); i++) {
            String newStr = removeCharAt(s, i);
        // Judge whether the deleted string is a palindrome string
            flag = isPdStr(newStr);
            if(flag){
                return true;
            }
        }
        return false;
    }

    /**
     * Returns the string after deleting the specified character
     *
     * @param s
     * @param pos
     * @return
     */
    public static String removeCharAt(String s, int pos) {
        return s.substring(0, pos) + s.substring(pos + 1);
    }

    /**
     * Determine whether it is palindrome string
     *
     * @param s
     * @return
     */
    public static boolean isPdStr(String s) {
        // Reverse string
        String reverseStr = new StringBuilder(s).reverse().toString();
        return s.equals(reverseStr);
    }
}

Here, two methods are extracted to judge whether a string is a palindrome string and obtain the string after deleting the specified character.

Submit code to LeetCode:

Because the test case is a very long string, our program exceeds the time limit, so violent exhaustion can not solve this problem.

Can you optimize this code?

In fact, we don't need to traverse the string from left to right and delete it exhaustively. We can define two pointers, one to the beginning and the other to the end, and then move them to the middle at the same time. Because the palindrome string is characterized by the same reading results from left to right and from right to left, if the characters passed by the two pointers are the same, It meets the characteristics of palindrome string; If not, consider whether the palindrome string is satisfied after deleting a character.

For example:

For such a string, we set two pointers at the beginning and end:

Judge whether the characters at the pointer positions are equal. If they are equal, the pointer i moves right and the pointer j moves left:

Continue to judge whether the characters at the pointer position are equal. Because they are equal, continue to move the pointer:

At this time, the pointer i has been greater than the pointer j, and the traversal ends. Therefore, it is concluded that the string is a palindrome string.

Let's take another example of characters that need to be deleted:

The character pointed to by pointer i is a and the character pointed to by pointer j is c. they are different, which shows that the string is not a palindrome string. How to delete a character to make it a palindrome string? It can be determined that the deleted character must be one of the two characters pointed to by pointer i and pointer j. because the two characters are different, the string is not a palindrome string. Therefore, no matter how the middle character can change this fact, delete one of them and compare it.

Here, it is assumed that the deleted character is c:

Now that the characters pointed to by the two pointers are the same, move the pointer:

The pointer coincides and the traversal ends.

The resulting code is as follows:

public class Solution {

    public static boolean validPalindrome(String s) {
        // Declaration header and footer pointers
        int i = 0;
        int j = s.length() - 1;
        // Start traversal
        while (i < j) {
            // If two pointers point to different characters, consider deleting one of them
            if (s.charAt(i) != s.charAt(j)) {
                // If deleting one of the characters can satisfy that the current string is a palindrome string, return true
                return isPdStr(s, i + 1, j) || isPdStr(s, i, j - 1);
            }
            // If two pointers point to the same character, move the beginning and end pointers
            ++i;
            --j;
        }
        return true;
    }

    /**
     * Determine whether it is palindrome string
     *
     * @param s
     * @return
     */
    public static boolean isPdStr(String s, int i, int j) {
        for (int k = i; k <= i + (j - i) / 2; ++k) {
            if (s.charAt(k) != s.charAt(j - k + i)) {
                return false;
            }
        }
        return true;
    }
}

Here is a method to judge whether a given string is a palindrome string. It is still judged by double pointers, but some details need to be considered, such as:

For such a string, if the character c is deleted, move the j pointer forward. At this time, i = 0 and j = 2:

Pass i and j to isPdStr() method for judgment. You only need to compare half of the string length, so you can get i + (j - i) / 2. First, (j - i) / 2 can calculate half of the string length. Why add i? This is because the characters on the left of the string are likely to have been deleted, so those characters cannot be calculated.

Similarly, when judging the characters of two pointers, the calculation method of tail pointer is also different: j - k + i.

Submit the code and pass the test: