解法一 使用HashMap
之所以会想到用HashMap是因为对于每个字母，若使用HashMap的方式去查找只有O(1)的开销，是最快的。这种解法的思路是将27个字母和对应行存入字典，遍历单词中的字母，一有不在同一行的就跳出。
public class Solution {
public String[] findWords(String[] words) {
String[] strs={"QWERTYUIOP","ASDFGHJKL","ZXCVBNM"};
Map<Character,Integer> dict=new HashMap<>();
for(int i=0;i<strs.length;i++){
for(int j=0;j<strs[i].length();j++){
dict.put(strs[i].charAt(j),i);
}
}
List<String> li=new LinkedList<>();
for(int i=0;i<words.length;i++){
int index=dict.get(words[i].toUpperCase().charAt(0));
for(int j=1;j<words[i].length();j++){
index=(index!=dict.get(words[i].toUpperCase().charAt(j))?-1:index);
if(index==-1)break;
}
if(index!=-1)li.add(words[i]);
}
return li.toArray(new String[0]);
}
}
解法二 使用List
ArrayList中indexof查找是遍历的方式，最差要经过54次比较才能找到M，只要测试集足够大，速率是慢于HashMap的。
public class Solution {
public String[] findWords(String[] words) {
String[] ref = new String[3];
ref[0] = "qwertyuiopQWERTYUIOP";
ref[1] = "asdfghjklASDFGHJKL";
ref[2] = "zxcvbnmZXCVBNM";
List<String> result = new ArrayList<String>();
for (int i = 0; i < words.length; i++) {
int j = 0;
for (; j < 3; j++) {
int index = ref[j].indexOf(words[i].charAt(0));
if (index >= 0) {
break;
}
}
int p = 1;
for (; p < words[i].length(); p++) {
if (ref[j].indexOf(words[i].charAt(p)) == -1) {
break;
}
}
if (p == words[i].length()) {
result.add(words[i]);
}
}
String[] res = new String[result.size()];
for(int i = 0; i < result.size(); i++) {
res[i] = result.get(i);
}
return res;
}
}
Tips
一些关于常用集合的类：
- HashMap:实现了Map接口，存储键值对。
- ArrayList:动态数组，默认容量为10，每次扩容50%。
- LinkedList:链表实现的数组。
- Vector:同步的ArrayList,适用于多线程的情况，每次扩容一倍。
- 泛型:List<String>和li.toArray(new String[0])都是泛型的应用。
leetcode连接
