loading...

Discussion on: Daily Challenge #29 - Xs and Os

Collapse
motss profile image
Rong Sen Ng

This can be done in linear time and linear space in terms of complexity by keeping track of the number of letter in a Map object as you traverse the string. Do note that the letter should be case insensitive which that actually gives us a hint that we can make each of the character to be always lowercased before using it as a cache key.

Pseudocode:

a = 'xoxo'
m = Map()
loop for each n in a {
l = n.toLowerCase()

m.set(l, 1) if not m.has(l)
else m.set(l, 1 + m.get(l))
}

return True if not m.has('x') and not m.has('o')

return m.get('x') == m.get('o');