Solution: Valid Palindrome

Problem Statement

A phrase is a palindrome if, after converting all uppercase letters into lowercase letters and removing all non-alphanumeric characters, it reads the same forward and backward. Alphanumeric characters include letters and numbers.

Given a string s, return true if it is a palindrome, or false otherwise.

Example 1:

Input: sentence = "A man, a plan, a canal, Panama!"
Output: true
Explanation: "amanaplanacanalpanama" is a palindrome.

Example 2:

Input: sentence = "Was it a car or a cat I saw?"
Output: true

.....

Like the course? Get enrolled and start learning!

Nabeel Keblawi

· 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]

Deepa Subramanian

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

Zachary Nelson

· 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

jonah butler

· a year ago

func (sol *Solution) isPalindrome(s string) bool {
    first, last := 0, len(s) - 1

    for first < last {
        r1, r2 := rune(s[first]), rune(s[last])

        if !unicode.IsLetter(r1) && !unicode.IsDigit(r1) {
            first++
            continue
        }

        if !unicode.IsLetter(r2) && !unicode.IsDigit(r2) {
            last--
            continue
        }

        if unicode.ToLower(r1) != unicode.ToLower(r2) {
            return false
        }

        first++
        last--
    }

    return true
}

Pretty similar to the original solution, but the conditional expressions with continue as opposed to the inner for loops feels a bit easier for me to follow.