leetcode month day 3: anagrams

Problem: two strings. Are they anagrams of each other?

Software engineer hat again: if these are arbitrary Unicode strings, then the right solution is count the characters in the first string, binning the counts by character, and then subtract the counts of the characters in the second string. If the characters are ASCII, then you can be clever and use the character value as an index into an array and do the same add/subtract algorithm…but someone will use a non-ASCII character, sooner or later. And the failure mode of clever is…well.

Score: bottom 15% in time and space, but I’ll take that for the vastly reduced need to worry about weird input. If we remove the conversion to string and use bytes, then it improves to 30%. The real win doesn’t happen until the conversion to arrays. I initially had a delete to remove counts that went to 0 and a check for counts that went negative (chars in t not in s) but there wasn’t a significant speedup.

func isAnagram(s string, t string) bool {
    // easiest way is to map the character counts into a hash.
    // if the two strings match, there should be no odd counts.
    if len(s) != len(t) {
        return false
    }

    charCounts := make(map[byte]int)
    for i := range(s) {
        charCounts[s[i]]++
    }
    for i := range(t) {
        x := string(t[i])
        charCounts[x]--
    }
    for _, count := range(charCounts) {
        if count != 0 {
            return false
        }
    }
    return true
}

Giving up and using an array of 256 ints, indexed by the int value of the bytes, it’s much faster: 93% on time, 98% on space. Good enough. I suppose you could use this on Unicode input, since it’s just looking at raw bytes. Depends on whether you have a character that can be represented in more than one way in Unicode.

The syntax for creating arrays continues to be a problem. I’m going to standardize on assigning the type followed by {} to the variable.

func isAnagram(s string, t string) bool {    if len(s) != len(t) {        return false    }    charCounts := [256]int{}    for i := range(s) {        charCounts[int(s[i])]++    }    for i := range(t) {        x := int(t[i])        charCounts[x]--    }    for _, count := range(charCounts) {        if count != 0 {            return false        }    }    return true}