125. Valid Palindrome

Problem Link

Check Palindrome by comparing starting and ending characters in string. You can easily do this by taking two pointers, pointing the respective position from start and end which should be same to form palindrome.

Pseudocode

• Initialize start and end pointers
• Iterate over the string using the pointers until they meet or cross each other over bound.

Runtime Complexity

Time: \(O(n)\), single iteration over string.

Space: \(O(1)\), constant space by two pointers.

PythonGo

class Solution:
    def isPalindrome(self, s: str) -> bool:
        l, r = 0, len(s)-1
        while l < r:
            if not s[l].isalnum():
                l+=1
            elif not s[r].isalnum():
                r-=1
            elif s[l].lower() != s[r].lower():
                return False
            else:
                l+=1
                r-=1
        return True

func isPalindrome(s string) bool {
    chars := []rune(s)
    l, r := 0, len(s)-1
    for l < r {
        for l < r && !unicode.IsDigit(chars[l]) && !unicode.IsLetter(chars[l]) {
            l++
        }
        for l < r && !unicode.IsDigit(chars[r]) && !unicode.IsLetter(chars[r]) {
            r--
        }
        if unicode.ToLower(chars[l]) != unicode.ToLower(chars[r]) {
            return false
        }
        l++
        r--
    }
    return true
}

Go Implementation note

Strings in Go are sequence of bytes , so when you access any particular index - it'll return the respective byte. While characters are represented using rune which represents a Unicode code point. Byte occupies 1 byte size while Rune can use upto 4 bytes size, which is why converting a byte using rune(.) isn’t always safe. It's safe for ASCII characters which fall within 1 byte range.

---