双指针模式解决回文问题

huangapple go评论57阅读模式
英文:

Two pointers pattern to solve palindrome problem

问题

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
};

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'.

英文:

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

<!-- begin snippet: js hide: false console: true babel: false -->

<!-- language: lang-js -->

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

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

        left++
        right--
    }

    return true
};

console.log(isPalindrome(&#39;racecar&#39;))
console.log(isPalindrome(&#39;Ceci n’est pas une palindrome&#39;))

<!-- end snippet -->

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

while(left &lt; 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'.

答案1

得分: 1

  1. 输入长度为偶数时
  2. 输入长度为奇数时

while(left &lt; right) 表示我们必须检查直到左指针越过右指针。在它越过之前,如果在任何时刻左指针和右指针处的字母不相同,那么输入不是回文。

现在,当输入长度为奇数时,您可以忽略中间元素,因为它没有任何匹配项。

如果要明确检查 arr[middle]==arr[middle],只需在 while 条件中包含相等性。 while(left&lt;=right)

英文:

Now there can be two cases for the input.

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

while(left &lt; 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&lt;=right)

答案2

得分: 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.

英文:

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

答案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?

huangapple
  • 本文由 发表于 2023年5月17日 22:18:03
  • 转载请务必保留本文链接:https://go.coder-hub.com/76273122.html
匿名

发表评论

匿名网友

:?: :razz: :sad: :evil: :!: :smile: :oops: :grin: :eek: :shock: :???: :cool: :lol: :mad: :twisted: :roll: :wink: :idea: :arrow: :neutral: :cry: :mrgreen:

确定