给你一个字符串数组 words ,只返回可以使用在 美式键盘 同一行的字母打印出来的单词。键盘如下图所示。
美式键盘 中:
- 第一行由字符 "qwertyuiop" 组成。
- 第二行由字符 "asdfghjkl" 组成。
- 第三行由字符 "zxcvbnm" 组成。
示例 1:
输入:words = ["Hello","Alaska","Dad","Peace"]
输出:["Alaska","Dad"]
方法一:哈希表
一眼看去一共三组不重复的表单,且输入字符串应全为一种表单里的元素,那么可以直接利用散列集合(hash set)的特性快速筛选符合要求的字符串。
private static Set<Character> set1 = new HashSet<>(16), set2 = new HashSet<>(16), set3 = new HashSet<>(16);
static {
char[] chars1 = new char[] {'q', 'w', 'e', 'r', 't', 'y', 'u', 'i', 'o', 'p'};
char[] chars2 = new char[] {'a', 's', 'd', 'f', 'g', 'h', 'j', 'k', 'l'};
char[] chars3 = new char[] {'z', 'x', 'c', 'v', 'b', 'n', 'm'};
for (char c : chars1) set1.add(c);
for (char c : chars2) set2.add(c);
for (char c : chars3) set3.add(c);
}
public String[] findWords(String[] words) {
ArrayList<String> list = new ArrayList<>();
for (String word : words) {
int i = 0, n = word.length();
Set<Character> set;
if (set1.contains(getAwfulChar(word.charAt(i)))) {
set = set1;
} else if (set2.contains(getAwfulChar(word.charAt(i)))) {
set = set2;
} else {
set = set3;
}
while (i < n && set.contains(getAwfulChar(word.charAt(i)))) ++ i;
if (i == n) list.add(word);
}
String[] result = new String[list.size()];
return list.toArray(result);
}
private static char getAwfulChar(char c) {
if ('a' <= c && c <= 'z') return c;
else return (char) (c+32);
}