leetcode day 16: ransom note

Given a magazine string, check to see if a ransomNote string can be composed by extracting characters from magazine. The count of ‘a’, ‘b’, ‘c’, etc. in magazine must be >= the count needed to compose ransomNote.

In another language, I might sort the strings and then compare them, but Go has no built-in string sorting, so putting the “I need to get this done” hat on, I chose building a map of characters in magazine and then progressively checking the letters in ransomNote to see if we either can’t find a needed letter, or run out.

I needed to go look up the syntax to convert a string to a rune array (it’s []rune(string), which is a weird-ass syntax), but otherwise it was pretty easy.

Not the most efficient possible: top 72% in speed, bottom 11% in memory, but I’d choose it if I was actually doing it in code I needed to get done. Also extremely straightforward.

Faster solutions take advantage of the characters a) being ASCII and b) being all lower-case; I’d argue against them in a real-world situation because any bad data would cause them to fall over with an array bounds issue. My solution could parse text in Nazca and still work.

func canConstruct(ransomNote string, magazine string) bool {
   // Add the magazine chars to a map of map[rune]int, incrementing
   // for each rune found.
   // walk through the note, decrementing the char counts as we go.
   // if we ever hit a rune that is not in the map, or whose count is 0,
   // then return false. Else return true.
   magazineMap := make(map[rune]int)
   for _, c := range([]rune(magazine)) {
       magazineMap[c]++
   }
   for _, c := range([]rune(ransomNote)) {
       if _, ok := magazineMap[c]; ok {
           if magazineMap[c] < 1 {
               return false
           } else {
               magazineMap[c]--
           }
       } else {
           // char not found
           return false
       }
   }
   return true
}