Recently I have been looking at data structures and algorithms, trying to sum up my debut ~

TL:DR

In the last article, we talked about an ordered array, so try iterating through it using Pointers

The essence of a pointer is to remember the progress of the traversal, thereby reducing the scope for invalid traversals.

Similarly, strings that are palindromes have natural symmetry and are good for using Pointers to narrow down traversal.

What is a palindrome

Palindrome: The exact same string read forward and backward.

Features: Symmetrical! Symmetrical! Symmetrical!

Quick API method for checking palindromes: STR =>str.split(”).reverse().join() === STR

Non-api naive methods: the left and right Pointers, as long as they are equal, move to the middle, iterate is palindrome, otherwise not palindrome

function isPalindrome(str) {
  let len = str.length;
  let L = 0;
  let R = len - 1;
  // The left pointer is always on the left
  while (L < R) {
    if(str[L] ! == str[R]) {return false;
    }
    L++;
    R--;
  }
  return true;
}
Copy the code

Practice: string questions in palindromes

Of course, if you don’t know what symmetry is, you might violently start with the first string and try to delete it, and then determine whether the rest is palindrome, which is certainly possible, but doesn’t take advantage of symmetry.

In fact, here, and to determine whether palindrome, left and right double pointer, when not equal, try to “skip” the left pointer character and right pointer character, see whether the string between [L+1, R] or [L, r-1] palindrome.

function validPalindrome(str) {
  const len = str.length;
  let L = 0;
  let R = len - 1;
  // Add an equality to the loop condition, so that the position after the loop is not equal
  while (L < R && str[L] === str[R]) {
    L++;
    R--;
  }
  // Determine whether a particular interval is a palindrome
  if (isPalindrome(L + 1, R) || isPalindrome(L, R - 1)) {
    return true;
  }
  return false;

  // Change the method slightly to a specific interval
  function isPalindrome(L, R) {
    while (L < R) {
      if(str[L] ! == str[R]) {return false;
      }
      L++;
      R--;
    }
    return true; }}Copy the code

Check out the official video

reference

  • The front-end algorithm and data structure of xiuyan