500. Keyboard Row

解法一 使用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

一些关于常用集合的类：

1. HashMap:实现了Map接口，存储键值对。
2. ArrayList:动态数组，默认容量为10，每次扩容50%。
3. LinkedList:链表实现的数组。
4. Vector:同步的ArrayList,适用于多线程的情况，每次扩容一倍。
5. 泛型:List<String>和li.toArray(new String[0])都是泛型的应用。
   leetcode连接