Set version : when we do set(string) = > python will automatically flatten them into single character Besides, for one word if its characters are in one row, it can be consider one row’s subset , hence set_w <= line1
class Solution:
def findWords(self, words: List[str]) -> List[str]:
"""
tc O(26+ W*L) sc O(26)
"""
line1,line2,line3 = set('qwertyuiop'), set('asdfghjkl'), set('zxcvbnm')
res = []
for w in words:
set_w = set(w.lower())
if set_w <= line1 or set_w <= line2 or set_w <= line3:
res.append(w)
return res
HashTable Version
class Solution:
def findWords(self, words: List[str]) -> List[str]:
"""
tc O(26+ W*L) sc O(26)
"""
d = {}
res = []
for c in 'qwertyuiop':
d[c] = 1
for c in 'asdfghjkl':
d[c] = 2
for c in 'zxcvbnm':
d[c] = 3
for w in words:
r = None
add = True
for ch in w:
ch = ch.lower()
if not r:
r = d[ch]
else:
if r != d[ch]:
add = False
break
if add:
res.append(w)
return res
Regex Version
from re import compile
class Solution:
def findWords(self, words: List[str]) -> List[str]:
return filter(compile('(?i)([qwertyuiop]*|[asdfghjkl]*|[zxcvbnm]*)$').match, words)