Topic describes

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

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

The sample

Example 1:

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

Example 2:

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

Their thinking

To determine whether it is a palindrome string is equivalent to whether the left and right sides of the string separated from the middle are equal, which can be understood as whether the string is symmetric about the center. Since it involves the left and right sides, then the first thought should be the double pointer.

Thinking a

  • For convenience, we might as well make the string all uppercase or lowercase first;
  • The left pointer moves from the first element of the string, the right pointer moves from the last element of the string,

The two hands move opposite each other;

  • So the question is, because strings contain Spaces and punctuation, what do we do?
  • So we can write a function to determine whether the current pointer refers to a letter or a number. If so, return true; Otherwise return false;
  • If the two Pointers are not equal, return false; if the two Pointers are not equal, return false. Equal, continue to compare, until the two Pointers meet, out of the loop;

Idea 2

An easy way to do this is to use a regular expression to replace all but the letters and digits in the string with nothing else, leaving only the numbers and letters in the string. There is no need to define another method, and then combine the double pointer to get the final solution.

AC code

Code 1

var isPalindrome = function(s) { s = s.toLowerCase() let i = 0, j = s.length - 1 while(i < j) { if(! isvalid(s[i])) { i++ continue } if(! isvalid(s[j])) { j-- continue } if(s[i] == s[j]) { i++ j-- } else { return false } } return true }; let isvalid = (str) => { return (str >= 'a' && str <= 'z') || (str >= '0' && str <= '9') }Copy the code

Code 2

Var isPalindrome = function(s) {// \W = function(s) {// \W = function(s) { / / equivalent to the '[^ A Za - z0-9 _]' s = s.r eplace (/ | _ \ W/g, "). The toLowerCase () the let I = 0, j = s.l ength - 1 while (I < j) {if (s [I]! = s[j]) { return false } i++ j-- } return true }Copy the code

conclusion

As for many problems I have done so far, I find that many of them are answered with double Pointers, so sometimes when I look at similar problems, it is easy to think of using double Pointers to solve problems. So still want to brush more algorithm, more grasp some algorithm ideas, start to be able to be more handy ah. The road is still going, come on!

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