Question 170425 in Javascript Question posted in
A very good W3school tutorial can be found here.

Can Javascript use two pointers to solve palindrome problems?

I want to solve the "palindrome" problem by using the ‘two pointers’ pattern. Here is the code that solves this problem:

var isPalindrome = function(s) {
    const newStr = s.toLowerCase().replace(/[^0-9a-z]/g, "")

    let left = 0
    let right = newStr.length-1
    
    while (left < right) {
        if (newStr[left] !== newStr[right]) {
            return false
        }

        left++
        right--
    }

    return true
};

console.log(isPalindrome('racecar'))
console.log(isPalindrome('Ceci n’est pas une palindrome'))

The above code is working as expected, but the problem is that I do not quite understand how this logic is working:

while(left < right)

Ensures the correct work to solve the palindrome problem. Say, we have this string ‘racecar’ and if we move left and right pointers to each other and if both pointers get to both of the ‘c’ next to ‘e’ then while loop will run LAST time but we miss ‘e’ and because we miss ‘e’ how can we be sure that two pointers solves palindrome problem? Can someone please clarify this?

I do not understand how two pointers pattern solve palindrome problem is we miss ‘e’ considering we have this string ‘racecar’.

Tags:

3

Answers


  1. 0

    A palindrome is a word that can be read from right to left and from left to right. When you have an odd number of letters in a word the middle letter should not match any other letter. therefore there is no need to check it. When left<right exists if the word has an odd number of letters the middle letter will not be checked

    Login or Signup to reply.
  2. 0

    Now there can be two cases for the input.

    1. Input is even in length
    2. Input is odd in length

    while(left < right) means that we have to check until the left pointer crosses the right pointer. Before it does if at any moment the letters are not same at left and right pointer, the input is not palindrome.

    now, when the input length is odd, you can just ignore the middle element since it does not have any counter match.

    If you want to explicitly check if arr[middle]==arr[middle] just include the equality in the while condition. while(left<=right)

    Login or Signup to reply.
  3. 0

    Think about it! If you are looking at all of the characters where the index of the left character is less than the index of the right character and they are the same, you don’t need to check the final case where the index of the left character at your index is equal to the index of the next right character at the same index. The fact that left index is the same as the right index means that you are comparing a character to itself which is always going to be equal. So, odd numbered strings you skip the middle character, and even number strings you check them all. Does this make sense?

    Login or Signup to reply.
Please signup or login to give your own answer.

Back To Top
Search