500 Keyboard Row

Given a List of words, return the words that can be typed using letters ofalphabeton 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.

The Idea:

  1. Check the row it belongs in.

  2. Confirm that all characters exist in that row.

bool contains_all(const unordered_set<char> &row, const string &word) 
{
    for (char i : word) {
        if (row.find(i) == row.end())
            return false;
    }

    return true;
}

vector<string> findWords(vector<string>& words) 
{
    const unordered_set<char> r1 = { 'q','w','e','r','t','y','u','i','o','p','Q','W','E','R','T','Y','U','I','O','P' };
    const unordered_set<char> r2 = { 'a','s','d','f','g','h','j','k','l', 'A','S','D','F','G','H','J','K','L' };
    const unordered_set<char> r3 = { 'z','x','c','v','b','n','m','Z','X','C','V','B','N','M'};

    vector<string> single_row_words;

    for (int i = 0; i < words.size(); i++) {
        string cur_word = words[i];

        // determine row
        if (r1.find(cur_word[0]) != r1.end()) {
            if (contains_all(r1, cur_word))
                single_row_words.push_back(cur_word);
        }
        else if (r2.find(cur_word[0]) != r2.end()) {
            if (contains_all(r2, cur_word))
                single_row_words.push_back(cur_word);
        }
        else {
            if (contains_all(r3, cur_word))
                single_row_words.push_back(cur_word);
        }
    }
    return single_row_words;
}


int main()
{
    vector<string> test_in;
    test_in = {"abdfs", "cccd", "a", "qwwewm"};
    print(findWords(test_in));

    test_in = { "Aasdfghjkl","Qwertyuiop","zZxcvbnm" };
    print(findWords(test_in));
}

Last updated