leetcode

Valid Palindrome solution using TypeScript

Below is my TypeScript solution to the LeetCode "Valid Palindrome" question.

Algorithm: This solution uses a two-pointer approach. It places two pointers, one on each end of the array. The pointers will then move towards the middle, skipping invalid characters, and compare their values with each other on each iteration. If all characters match, the string can be considered a palindrome.

Time Complexity: Because there will be, at most, one iteration over the array, the time complexity is O(n) where n represents the number of elements in the array.

Space Complexity: Because this solution uses a constant amount of space, the time complexity is O(1).

/**
 * Valid Palindrome
 * Given a string, determine if it is a palindrome, 
 * considering only alphanumeric characters and ignoring cases.
 *
 * Time Complexity: O(n)
 * Space Complexity: O(1)
 *
 * isPalindrome("taco cat") // true
 * isPalindrom("race a car") // false
 */
function isPalindrome(s: string): boolean {
    let j = s.length - 1;
    for (let i = 0; i < j; i++, j--) {
        while (i < j && !isAlphaNumeric(s[i])) {
            i++;
        }
        while (i < j && !isAlphaNumeric(s[j])) {
            j--;
        }
        if (i < j && s[i].toLowerCase() !== s[j].toLowerCase()) {
            return false;
        }
    }
    return true;
};

function isAlphaNumeric(value: string) {
    return value.match(/^[A-Za-z0-9]+$/);
}

more LeetCode posts