June 2nd 2023

Valid Palindrome — Typescript

Problem Description

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: s = "A man, a plan, a canal: Panama"
Output: true
Explanation: "amanaplanacanalpanama" is a palindrome.

Example 2:

Input: s = "race a car"
Output: false
Explanation: "raceacar" is not a palindrome.

Example 3:

Input: s = " "
Output: true
Explanation: s is an empty string "" after removing non-alphanumeric characters.
Since an empty string reads the same forward and backward, it is a palindrome.

Constraints:

1 <= s.length <= 2 * 105 s consists only of printable ASCII characters.

Solution

// Util functions
function expect(description: string, test: boolean) {
    if (test) {
        console.log(`✅ ${description}`)
    } else {
        console.log(`❌ ${description}`)
    }
}

function isPalindrome(s: string): boolean {
    const chars = s
        .split("")
        .map(s => s.toLocaleLowerCase())
        .filter(character => character.match(/[a-zA-Z0-9]/))

    const lengthOfString = chars.length

    if (lengthOfString == 0) {
        return true
    }

    for (var i = 0; i < Math.floor(chars.length / 2); i++) {
        const charA = chars[i]
        const charB = chars[lengthOfString - i - 1]

        if (charA !== charB) {
            return false
        }
    }

    return true
};

//3: T(T)T mid = 1
//4: TT(*)TT mid = 2
//5: TT(T)TT mid = 2
// mid = floor(length/2)

expect("A man, a plan, a canal: Panama is a palindrome", isPalindrome("A man, a plan, a canal: Panama"))
expect("aa is a palindrome", isPalindrome("aa"))
expect("aba is a palindrome", isPalindrome("aba"))
expect("a is a palindrome", isPalindrome("a"))
expect(",,,;, is a palindrome", isPalindrome(",,,;,"))
expect("race a car is not a palindrome", !isPalindrome("race a car"))
expect("0P is not a palindrome", !isPalindrome("0P"))

Discussion

This is readable but not fast. It would be faster replace the characters with a regular expression, reverse the string and compare. For stupidly enormous strings that would be a memory problem but for non-adversial strings it would be fine.