Keyboard Row – LeetCode Solution Java , Python 3, Python 2 , C , C++, Best and Optimal Solutions , All you need.
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"]
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).
C++ Keyboard Row LeetCode Solution
class Solution {
public:
vector<string> findWords(vector<string>& words) {
vector<int> dict(26);
vector<string> rows = {"QWERTYUIOP", "ASDFGHJKL", "ZXCVBNM"};
for (int i = 0; i < rows.size(); i++) {
for (auto c : rows[i]) dict[c-'A'] = 1 << i;
}
vector<string> res;
for (auto w : words) {
int r = 7;
for (char c : w) {
r &= dict[toupper(c)-'A'];
if (r == 0) break;
}
if (r) res.push_back(w);
}
return res;
}
};
Java Keyboard Row LeetCode Solution
public class Solution {
public String[] findWords(String[] words) {
String[] strs = {"QWERTYUIOP","ASDFGHJKL","ZXCVBNM"};
Map<Character, Integer> map = new HashMap<>();
for(int i = 0; i<strs.length; i++){
for(char c: strs[i].toCharArray()){
map.put(c, i);//put <char, rowIndex> pair into the map
}
}
List<String> res = new LinkedList<>();
for(String w: words){
if(w.equals("")) continue;
int index = map.get(w.toUpperCase().charAt(0));
for(char c: w.toUpperCase().toCharArray()){
if(map.get(c)!=index){
index = -1; //don't need a boolean flag.
break;
}
}
if(index!=-1) res.add(w);//if index != -1, this is a valid string
}
return res.toArray(new String[0]);
}
}
Python 3 Keyboard Row LeetCode Solution
class Solution(object):
def findWords(self, words):
"""
:type words: List[str]
:rtype: List[str]
"""
a=set('qwertyuiop')
b=set('asdfghjkl')
c=set('zxcvbnm')
ans=[]
for word in words:
t=set(word.lower())
if a&t==t:
ans.append(word)
if b&t==t:
ans.append(word)
if c&t==t:
ans.append(word)
return ans
Array-1180
String-562
Hash Table-412
Dynamic Programming-390
Math-368
Sorting-264
Greedy-257
Depth-First Search-256
Database-215
Breadth-First Search-200
Tree-195
Binary Search-191
Matrix-176
Binary Tree-160
Two Pointers-151
Bit Manipulation-140
Stack-133
Heap (Priority Queue)-117
Design-116
Graph-108
Simulation-103
Prefix Sum-96
Backtracking-92
Counting-86
Sliding Window-73
Linked List-69
Union Find-66
Ordered Set-48
Monotonic Stack-47
Recursion-43
Trie-41
Binary Search Tree-40
Divide and Conquer-40
Enumeration-39
Bitmask-37
Queue-33
Memoization-32
Topological Sort-31
Geometry-30
Segment Tree-27
Game Theory-24
Hash Function-24
Binary Indexed Tree-21
Interactive-18
Data Stream-17
String Matching-17
Rolling Hash-17
Shortest Path-16
Number Theory-16
Combinatorics-15
Randomized-12
Monotonic Queue-9
Iterator-9
Merge Sort-9
Concurrency-9
Doubly-Linked List-8
Brainteaser-8
Probability and Statistics-7
Quickselect-7
Bucket Sort-6
Suffix Array-6
Minimum Spanning Tree-5
Counting Sort-5
Shell-4
Line Sweep-4
Reservoir Sampling-4
Eulerian Circuit-3
Radix Sort-3
Strongly Connected Componen-t2
Rejection Sampling-2
Biconnected Component-1