Teaching Kids Programming: Videos on Data Structures and Algorithms
Given an array of strings words, return the words that can be typed using letters of the alphabet on only one row of American keyboard like the image below.
In the American keyboard:
the first row consists of the characters “qwertyuiop”,
the second row consists of the characters “asdfghjkl”, and
the third row consists of the characters “zxcvbnm”.Example 1:
Input: words = [“Hello”,”Alaska”,”Dad”,”Peace”]
Output: [“Alaska”,”Dad”]American Keyboard Layout
Example 2:
Input: words = [“omk”]
Output: []Example 3:
Input: words = [“adsdf”,”sfd”]
Output: [“adsdf”,”sfd”]Constraints:
1 <= words.length <= 20
1 <= words[i].length <= 100
words[i] consists of English letters (both lowercase and uppercase).
Words Typed using One Keyboard Row
We store the characters for first, second and third rows in three sets respectively. Storing in sets provide O(1) constant lookup otherwise it will be linear to the number of the characters for the row.
We can use the all keyword to check if all the characters from a word come from a specific row only.
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 | class Solution: def findWords(self, words: List[str]) -> List[str]: ans = [] first = set("qwertyuiop") second = set("asdfghjkl") third = set("zxcvbnm") def singleRow(w): return all(c in first for c in w) or \ all(c in second for c in w) or \ all(c in third for c in w) for w in words: if singleRow(w.lower()): ans.append(w) return ans |
class Solution:
def findWords(self, words: List[str]) -> List[str]:
ans = []
first = set("qwertyuiop")
second = set("asdfghjkl")
third = set("zxcvbnm")
def singleRow(w):
return all(c in first for c in w) or \
all(c in second for c in w) or \
all(c in third for c in w)
for w in words:
if singleRow(w.lower()):
ans.append(w)
return ansAlternatively, we can check if the set (of the word) is a subset of first, second or third row.
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 | class Solution: def findWords(self, words: List[str]) -> List[str]: ans = [] first = set("qwertyuiop") second = set("asdfghjkl") third = set("zxcvbnm") def singleRow(w): s = set(w) return s.issubset(first) or \ s.issubset(second) or \ s.issubset(third) for w in words: if singleRow(w.lower()): ans.append(w) return ans |
class Solution:
def findWords(self, words: List[str]) -> List[str]:
ans = []
first = set("qwertyuiop")
second = set("asdfghjkl")
third = set("zxcvbnm")
def singleRow(w):
s = set(w)
return s.issubset(first) or \
s.issubset(second) or \
s.issubset(third)
for w in words:
if singleRow(w.lower()):
ans.append(w)
return ansThe American Keyboard contains 26 characters only. Thus, we can also store the row number for each character. Then we have to check if the row number set contains only 1 number (only 1 row). This may simplify the implementation:
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 | class Solution: def findWords(self, words: List[str]) -> List[str]: ans = [] rows = [set("qwertyuiop"), set("asdfghjkl"), set("zxcvbnm")] def singleRow(w): r = set() for x in w: for i, c in enumerate(rows): if x in c: r.add(i) break return len(r) == 1 for w in words: if singleRow(w.lower()): ans.append(w) return ans |
class Solution:
def findWords(self, words: List[str]) -> List[str]:
ans = []
rows = [set("qwertyuiop"), set("asdfghjkl"), set("zxcvbnm")]
def singleRow(w):
r = set()
for x in w:
for i, c in enumerate(rows):
if x in c:
r.add(i)
break
return len(r) == 1
for w in words:
if singleRow(w.lower()):
ans.append(w)
return ans–EOF (The Ultimate Computing & Technology Blog) —
a WordPress rating system
Last Post: Teaching Kids Programming - Sum of Geometric Progression (Math Proof and Python Function)
Next Post: Teaching Kids Programming - Algorithms to Rotate an Array