【leetcode】500. Keyboard Row

题目

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.

分析

输入一组单词，用vector容器封装，判断每个单词的所有字母是否在键盘的同一行，如果在同一行，留在vector中，否则移除，最后输出vector

思路

1. 建立键盘三行的大小写字母表
2. 遍历vector内的单词
3. 对于每一个单词先确定首字母所在行号，再依次查看后面的字母是否跟首字母在同一行，一旦不一致，立刻从vector中删除该单词

问题总结

1. 一开始上手打算用字符数组存放键盘表，折腾了好久发现一个严重的问题：数组作为参数传递时，传递的是指针，这时候再用sizeof()来求数组的长度实际上求得的是指针的长度，而非数组长度，所以数组作为传递参数时需要将其长度也作为一个参数传递，后续运算时才不会出错，所以改用string存储每一行字母。
2. vector中用earse()删除元素时，返回值为：指向被删除元素的下一个元素的iterator，外层如果用for循环iter++,容易出现越界情况,所以采用了while循环

代码

class Solution {
public:
    vector<string> findWords(vector<string>& words) {
        string str1 = "qwertyuiopQWERTYUIOP";
        string str2 = "asdfghjklASDFGHJKL";
        string str3 = "zxcvbnmZXCVBNM";
        vector<string>::iterator it = words.begin();
        int logo = 0;
        while (it != words.end())
        {
            int linenum = 0;
            int linenumt = 0;
            string word = *it;
            if (word.length() == 1) {
                it++;
                continue;
            }
            else{
                int wordlen = word.size();
            char shouzimu = word[0];
            string::size_type idx = str1.find(shouzimu);
            if (idx != string::npos)
                linenum = 1;
            else
            {
                string::size_type idx = str2.find(shouzimu);
                if (idx != string::npos)
                    linenum = 2;
                else
                {
                    string::size_type idx = str3.find(shouzimu);
                    if (idx != string::npos)
                        linenum = 3;
                }
            }

            //判断剩余字母是否跟首字母处于同一行
            for (int i = 1; i < wordlen; i++) {
                char zimu = word[i];
                string::size_type idx = str1.find(zimu);
                if (idx != string::npos)
                    linenumt = 1;
                else
                {
                    string::size_type idx = str2.find(zimu);
                    if (idx != string::npos)
                        linenumt = 2;
                    else
                    {
                        string::size_type idx = str3.find(zimu);
                        if (idx != string::npos)
                            linenumt = 3;
                    }
                }
                if (linenumt != linenum) {
                    it = words.erase(it);//删除当前元素，返回值：指向下一个元素的iter
                    logo = 1;
                    break;
                }
                else {
                    logo = 0;
                    continue;
                }
            }
            if (logo == 0)
            {
                it++;
            }
        }
            }
            
        return words;
    }
};

改进

用STL中的unordered_set采用hash表的存储方式，查找时间复杂度最优可达常数，但尝试后并没有实质上的改变，可能是因为数据量不够大，没有凸显出来他的优势。

class Solution {
public:
    vector<string> findWords(vector<string>& words) {
    
        unordered_set<char> row1 {'q', 'w', 'e', 'r', 't', 'y','u', 'i', 'o', 'p'};
        unordered_set<char> row2 {'a', 's', 'd', 'f', 'g', 'h', 'j', 'k', 'l'}; 
        unordered_set<char> row3 { 'z', 'x', 'c', 'v', 'b' ,'n', 'm'};
        vector<unordered_set<char>> rows {row1, row2, row3};
        
        vector<string> validWords;
        for(int i=0; i<words.size(); ++i){
            int row=0;
            
            for(int k=0; k<3; ++k){
                if(rows[k].count((char)tolower(words[i][0])) > 0) row = k;
            }
            
            validWords.push_back(words[i]);
            for(int j=1; j<words[i].size(); ++j){
                if(rows[row].count((char)tolower(words[i][j])) == 0){
                    validWords.pop_back();
                    break;
                }
            }
            
        }
        return validWords;
    }
};

结果

上面两种方法