Leetcode – [125] Verify palindrome string | brush question punch

I obtained the topic through the LEetcode plug-in of IDEA, so the topic description basically has the annotation symbol

1. Topic description

 * // [125] Verify the palindrome string
 * // Given a string, verify that it is a palindrome string. Only alphanumeric characters are considered.
 * //
 * // Note: In this case, we define an empty string as a valid palindrome string.
 * //
 * / / example 1:
 * //
 * // Enter: "A man, A plan, A canal: Panama"
 * // Output: true
 * //
 * //
 * / / example 2:
 * //
 * // Enter: "race a car"
 * // Output: false
 * //
 * // Related Topics Double pointer string
Copy the code

2. Analysis of ideas

[9] return true if all of them match, false if any of them do not match

The main difference is that there may be non-numeric, non-alphabetic content to skip, mainly in the implementation of this part.

The following code uses two methods:

1. Character. IsLetterOrDigit () method (PS: this method will it also as Chinese letters, the Letter) 2. Manual implementationCopy the code

3. The AC code

public class No125 {
    public boolean isPalindrome(String s) {
        return method1(s);
// return method2(s);
    }

    Call the JDK Character isLetterOrDigit method to determine if the string is in the range of letters and digits@param s
     * @return* /
    private boolean method1(String s) {
        s = s.toLowerCase();
        char[] c = s.toCharArray();
        int l = 0;
        int r = s.length()-1;
        // If the pointer on the left is smaller than the pointer on the right, continue to check, and slowly move towards the middle
        while(l < r) {
            if(! isLetterOrDigit(c[l])) { l++; }else if(! isLetterOrDigit(c[r])) { r--; }else if(c[l++] ! = c[r--]) {return false; }}return true;
    }

    /** * Character (); /** * Character (); /** * Character (); https://www.compart.com/en/unicode/category *@param codePoint
     * @return* /
    public static boolean isLetterOrDigit(int codePoint) {
        return(((// Assign the value of Letter, and take the union
                    (1 << Character.UPPERCASE_LETTER) |
                      (1 << Character.LOWERCASE_LETTER) |
                      (1 << Character.TITLECASE_LETTER) |
                      (1 << Character.MODIFIER_LETTER) |
                      (1 << Character.OTHER_LETTER) |
                      (1 << Character.DECIMAL_DIGIT_NUMBER)
                    // with the corresponding character
                ) >> Character.getType(codePoint)
            ) & 1 ) != 0;
    }

    /** * from leetCode solution [no function calls in the handwritten version] ** Mainly encapsulates two methods, IsOK and equal * isOK - Characters fall within the range of letters and digits * equal - Case insensitive * * Execution time :3 ms, beating 92.60% of Java users * Memory consumption :38.5 MB, beating 70.62% of Java users * *@param s
     * @return* /
    public boolean method2(String s) {
        int i=0,j=s.length()-1;
        while(i<j){
            char a=s.charAt(i),b=s.charAt(j);
            if(isOK(a)&&isOK(b)&&! equal(a,b))return false;
            if(! isOK(a)&&i<j){i++;continue; }if(! isOK(b)&&i<j){j--;continue; }if(equal(a,b)&&i<j){i++; j--;continue; }if(! equal(a,b)&&i<j)return false; i++; j--; }return i>=j;
    }

    /** * ignores the case constraint **@param a
     * @param b
     * @return* /
    public boolean equal(char a,char b){
        if('a'<=a&&a<='z')a-='a';
        if('A'<=a&&a<='Z')a-='A';
        if('a'<=b&&b<='z')b-='a';
        if('A'<=b&&b<='Z')b-='A';
        return a==b;
    }

    /** * letters or numbers **@param c
     * @return* /
    public boolean isOK(char c){
        return ('a'<=c&&c<='z') | | ('A'<=c&&c<='Z') | | ('0'<=c&&c<='9'); }}Copy the code

4. To summarize

A little reflection: No matter when doing problems or projects, I often need the help of many tool classes when implementing functions, so that I often encapsulate many tool classes by myself. In fact, a lot of functionality may be included in the imported dependencies, or the JDK comes with it, so you can pay a little attention to avoid code duplication and keep your code clean.

This article is participating in the “Nuggets 2021 Spring Recruitment Campaign”, click to see the details of the campaign