Keyboard Row

https://leetcode.com/problems/keyboard-row/description/

Given a List of words, return the words that can be typed using letters of alphabet on only one row's of American keyboard like the image below.

Thoughts

判断一个单词内所有characters是否在同一行，也就是判断一堆元素是否在同一个set, 可以用union find. .

也可以让每个元素和对应的集合号放入map.

Code

class Solution {
    public String[] findWords(String[] words) {
        Map<Character, Integer> map = new HashMap<>();
        for (char c : "qQwWeErRtTyYuUiIoOpP".toCharArray()) {
            map.put(c, 1);
        }
        for (char c : "aAsSdDfFgGhHjJkKlL".toCharArray()) {
            map.put(c, 2);
        }
        for (char c : "zZxXcCvVbBnNmM".toCharArray()) {
            map.put(c, 3);
        }
        List<Integer> res = new ArrayList<>();
        for (int i = 0; i < words.length; i++) {
            boolean valid = true;
            String word = words[i];
            for (int j = 1; j < word.length(); j++) {
                if (map.get(word.charAt(j)) != map.get(word.charAt(j - 1))) {
                    valid = false;
                    break;
                }
            }
            if (valid) {
                res.add(i);
            }
        }

        String[] result = new String[res.size()];
        for (int i = 0; i < res.size(); i++) {
            result[i] = words[res.get(i)];
        }

        return result;
    }
}

Analysis

时间复杂度O(n).