leetcode month day 3: palindrome

I’m perceiving a pattern in my failures here and it is 100% “did you absolutely understand the requirements”.

Detecting a palindromic string was the easy part: just put an index at the end and the beginning, and march them toward the middle. If they meet or pass each other, then we succeeded. If at any point the characters at the indexes don’t match, we fail.

The problematic part was the cleanup of the initial string. Lowercasing wasn’t bad, though I had to look up where the function lived (it’s strings.ToLower()). Filtering the input was harder. I had to go check Stack Overflow and found this code, which is very nice and will go in my personal toolbox:

func cleanup(str string) string {
    return strings.Map(func(r rune) rune {
        if !unicode.IsDigit(r) && !unicode.IsLetter(r) {
            return -1
        }
        return r
    }, str)
}

The strings.Map function is really nice for “do something for every rune in a string”, especially since the special -1 return value says “drop this character”. Can do just about any transliteration you want with that! The unicode.IsDigit function highlights my “you did not read the instructions” error: I assumed that it would be alpha only, and that was incorrect; it was alphanumeric input.

I did spot a useful optimization: if the string is less than two characters long, by definition it’s a palindrome, so we can skip scanning it altogether.

Otherwise the algorithm I coded to scan was right the first time.

How’d I do comparatively? Meh. Runtime in the bottom 50%, memory in the top 60%. I think the lowercase followed by the cleanup is the culprit, and doing it all in one loop would be faster. I don’t think it’s as clear.

I tried a couple variations, and all of them are worse:

• Reverse the string and compare it to itself
• Inline the cleanup

This just may be something that Go kind of sucks at doing.

func isPalindrome(s string) bool {
    // lowercase, skim out all non-alpha characters
    s = strings.ToLower(s)
    s = spaceMap(s)

    if len(s) < 2 {
        return true
    }
    begin := 0
    end := len(s) - 1

    for {
        if begin > end {
            return true
        }
        if begin == end {
            return true
        }
        if s[begin] != s[end] {
            return false
        }
        begin++
        end--
    }
}

func spaceMap(str string) string {
    return strings.Map(func(r rune) rune {
        if !unicode.IsDigit(r) && !unicode.IsLetter(r) {
            return -1
        }
        return r
    }, str)
}