[LeetCode] 500. Keyboard Row

轉自LeetCode

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.

Example 1:

Input: ["Hello", "Alaska", "Dad", "Peace"]
Output: ["Alaska", "Dad"]

Note:

1. You may use one character in the keyboard more than once.
2. You may assume the input string will only contain letters of alphabet.

<Solution>

想法如下

• 將每個 row 做分群。可以用 set 或是 bit mask，這次使用 bit mask

• 分群 : QWERTYUIOP -> 001，ASDFGHJKL -> 010，ZXCVBNM -> 100

• 將每個字串裡面的字元，對 mask = 111 做 AND，如果最後 mask不為 0，就是要的答案

code 如下

C++(參考解法)

	class Solution {
	public:
	vector<string> findWords(vector<string>& words) {
	int table[26];
	const string rows[3] = {"QWERTYUIOP", "ASDFGHJKL", "ZXCVBNM"};
	//>> QWERTYUIOP -> 001
	//>> ASDFGHJKL -> 010
	//>> ZXCVBNM -> 100
	for(int i = 0; i < 3; i++) {
	for(const auto &c : rows[i]) {
	table[c - 'A'] = 1 << i;
	}
	}
	int mask;
	vector<string> ans;
	for(const auto &s : words) {
	mask = 7; //>> 111
	for(const auto &c : s) {
	mask &= table[toupper(c) - 'A'];
	if(mask == 0) {
	break;
	}
	}
	if(mask != 0) {
	ans.push_back(s);
	}
	}
	return ans;
	}
	};

view raw keyboardRow.cpp hosted with ❤ by GitHub

Java

	class Solution {
	public String[] findWords(String[] words) {
	int[] table = new int[26];
	final String[] rows = new String[]{"QWERTYUIOP", "ASDFGHJKL", "ZXCVBNM"};
	//>> QWERTYUIOP -> 001
	//>> ASDFGHJKL -> 010
	//>> ZXCVBNM -> 100
	for(int i = 0; i < 3; i++) {
	for(final char c : rows[i].toCharArray()) {
	table[c - 'A'] = 1 << i;
	}
	}
	int mask;
	ArrayList<String> ans = new ArrayList<>();
	for(final String s : words) {
	mask = 7;
	for(final char c : s.toCharArray()) {
	mask &= table[Character.toUpperCase(c) - 'A'];
	if(mask == 0) {
	break;
	}
	}
	if(mask != 0) {
	ans.add(s);
	}
	}
	return ans.toArray(new String[0]);
	}
	}

view raw keyboardRow.java hosted with ❤ by GitHub