Title: Validate palindrome string

Subject address: leetcode-cn.com/problems/va…

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.

Example 1:

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

Example 2:

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

solution

First, double pointer collision

  • Convert first to lowercase characters, and then double pointer collisions verify palindromes
/ * * *@param {string} s
 * @return {boolean}* /
var isPalindrome = function (s) {
  const str = s.replace(/[^a-zA-Z0-9]/g."").toLocaleLowerCase()
  let i = 0,
    j = str.length - 1
  while (i <= j) {
    if(str[i++] ! == str[j--]) {return false}}return true
}
Copy the code

Two-pointer collisions for the for loop

// * Use a for loop to validate a palindrome string

/ * * *@param {string} s
 * @return {boolean}* /
var isPalindrome = function (s) {
  const str = s.replace(/[^a-zA-Z0-9]/g.' ').toLocaleLowerCase()
  for (let i = 0, j = str.length - 1; i <= j; i++, j--) {
    if(str[i] ! == str[j]) {return false}}return true
};
Copy the code

Three, divide the two halves to compare whether they are equal

/ * * *@param {string} s
 * @return {boolean}* /
var isPalindrome = function (s) {
  const str = s.replace(/[^a-zA-Z0-9]/g."").toLocaleLowerCase()
  if(str.length <= 1) {return true
  }
  const halfLength = Math.floor(str.length / 2)
  const left = str.slice(0, halfLength)
  let right = str.slice(-halfLength)
  return left === right.split("").reverse().join("")}Copy the code
  • The basis for comparison is if I have odd lengths likeabncnba, length 7,Math.floor(str.length/2)Is 3, and the left hand side is cutstr.slice(0, halfLength)forabn, according to the string in jssliceProperty, if negative and null are received, the incoming length is truncated from the tail, as shown below:

  • So you get the other half of the string, if it’s even length, you ignore the middle character, you get the same effect.

The test case

// Test case
let test = "A man, a plan, a canal: Panama"

console.time("Execution time")
console.log(isPalindrome(test))
console.log(isPalindrome1(test))
console.timeEnd("Execution time")
Copy the code

conclusion

  • A direct return in a while terminates the loop directly, as does a for loop
  • The slice method of a string can accept negative values that represent the length of the character truncated from the end

instructions

  1. The GitHub address has been synchronized and the code can be copied for debugging.
  2. Summarized a set of effective front-end painless brush problem project, which can help algorithm white smooth start, see Leetcode-js-roadmap, hope to help front-end partners brush problem from scratch

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