This article is participating in the “Java Theme Month – Java Brush questions punch card”, see the activity link for details

Validates palindrome strings

Topic describes

Validating palindrome strings (LeetCode 125)

Given a string, verify that it is a palindrome string, considering only alphanumeric characters, regardless of letter case.

In this case, we define an empty string as a valid palindrome string.

Example 1:

Input: "A man, A plan, A canal: Panama" Output: trueCopy the code

Example 2:

Input: "race a car" Output: falseCopy the code

Thought analysis

Subject test is commonly used in language characters (string) the use of the relevant API, mentioned in the title only consider letters and numeric characters, ignore letter case, involving Character. IsLetterOrDigit and Character toLowerCase these two apis, In this case, we use the double pointer solution, using the head and tail pointer, only consider the letter and number characters, if not, respectively move the pointer, and then convert to lowercase for comparison, to determine whether it is a palindrome string. The time complexity of the solution is O(n){O(n)}O(n), and the space complexity is O(1){O(1)}O(1).

The code shown

Solution: Use double Pointers (head and tail Pointers), skip non-alphanumeric characters and convert them to lowercase characters for comparison. The time complexity is O(n){O(n)}O(n), and the space complexity is O(1){O(1)}O(1).

public boolean isPalindrome(String s) {
        String temp = s.trim();
        int length = temp.length();
        int head = 0;
        int tail = length - 1;
        while(head < tail){
            while(head < tail && ! Character.isLetterOrDigit(temp.charAt(head))){ head++; }while(head < tail && ! Character.isLetterOrDigit(temp.charAt(tail))){ tail--; }if(Character.toLowerCase(temp.charAt(head)) == Character.toLowerCase(temp.charAt(tail))){
                head++;
                tail--;
            } else {
                return false; }}return true;
}
Copy the code

palindrome

Topic describes

Palindromes (LeetCode 9)

Given an integer x, return true if x is a palindrome integer; Otherwise, return false. Palindromes are integers that read in positive (left to right) and backward (right to left) order. For example, 121 is palindrome and 123 is not.

Example 1:

Input: x = 121 Output: trueCopy the code

Example 2:

Input: x = -121 Output: false Description: Read from left to right. The value is -121. Read from right to left, 121-. So it's not a palindrome number.Copy the code

Example 3:

Input: x = 10 Output: false Description: Read from right to left, 01. So it's not a palindrome number.Copy the code

Example 4:

Input: x = -101 Output: falseCopy the code

Advanced: Can you solve this problem by not converting integers to strings?

Thought analysis

Above the problem we verified the palindrome string, this problem is to determine whether palindrome, if the string to convert the palindrome, subject becomes very simple, but it is best not to do so, the interviewer must also don’t want to see this answer, at the same time also mentioned a negative number in the title and some other conditions not palindrome Numbers, attention should be paid to these judgments. Also be aware of overflow problems caused by string reversals, so consider only half-reversals.

For example, by typing 1221, we can reverse the second half of the number “1221” from “21” to “12” and compare it with the first half of the number “12” because they are the same, we know that the number 1221 is a palindrome.

For the number 1221, if we execute 1221%10, we will get the last digit 1. To get the second to last digit, we can remove the last digit from 1221 by dividing it by 10, 1221/10 = 122, and then find the remainder of the result divided by 10. 122%10 = 2, you get the second to last number. If we multiply the last digit by 10 and add the second-to-last digit, 1 * 10 + 2 = 12, we get the inverted number we want. If we continue this process, we will get more inverted digits.

Now the question is, how do we know that the number of digits in the reversal has reached half the number of digits in the original number?

Since we keep dividing the original number by 10 and multiplying the inverted number by 10, when the original number is less than or equal to the inverted number, it means we have processed half of the digits.

The time complexity of this solution is O(logn){O(logn)}O(logn). For each iteration, we divide the input by 10, so the time complexity is O(logn){O(logn)}O(logn). The space complexity is O(1){O(1)}O(1).

The code shown

Solution: The time complexity of this solution is O(logn){O(logn)}O(logn), and the space complexity is also O(1){O(1)}O(1).

    public boolean isPalindrome(int x) {
        if(x < 0|| (x ! =0 && x % 10= =0)) {return false;
        }
        int reverseNumber = 0;
        while(x > reverseNumber){
            reverseNumber = reverseNumber * 10 + x % 10;
            x = x / 10;
        }
        return x == reverseNumber || (reverseNumber / 10 == x);
     }
Copy the code

conclusion

Verifying palindrome string and palindrome number are both very important, which is a common kind of question in the interview. In verifying palindrome string, double pointer solution can be used, but when judging palindrome number, it should be noted that it should not be converted into a string, and other ways should be used to answer it.