Grokking the Coding Interview: Patterns for Coding Questions
Vote

0% completed

​

Solution: Valid Palindrome

.....

.....

.....

Like the course? Get enrolled and start learning!
A

Anonymous

· 2 years ago

There is a much simpler way to solve this problem and maintain O(n) Time and O(1) space complexity

class Solution {
  isPalindrome(s) {
    s = s.toLowerCase().replace(/[^a-z0-9]/g, '');
    let l = 0;
    let r = s.length - 1;

    while (l < r) {
      if (s[l] !== s[r]) return false
      l++
      r--
    }
return true;

}

}

Show 1 reply
A

Anonymous

· 2 years ago

I used only 2 lines of code, but it's O(n) space complexity not O(1) in the course solution. And it's also Python, which may not be doable in other languages.

    tmp = ''.join([char for char in s if char.isalnum()]).lower()
    return tmp == tmp[::-1]
A

Anonymous

· 3 years ago

The regular expression given in the solution is wrong. It should be "/^[A-Za-z0-9]/g"

class Solution {
// tow pointer solution
  isPalindrome(s) {
    let left = 0, right = s.length -1;

    while(left < right){

        while(left < right && !s[left].match(/^[A-Za-z0-9]/g )) {
            left++
        }
        while(left < right && !s[right].match(/^[A-Za-z0-9]/g )) {
            right--
        }
        if(s[left].toLowerCase() != s[right].toLowerCase())
            return false
            left++
            right--
    }
    // two pointers cross over
    return true
  }
}

Reading Progress

0%

Vote for new content