LeetCode 500: Keyboard Row

Difficulty: Easy

Tags: Hash Table

问题描述

给出一个 string 型的数组，判断其中的单词的所有字母是不是来自键盘的同一行，如果是的话，将其输出。

解决方案

直接模拟。

▷ Time Complexity: O(n) n 是 words 中单词的数量

▷ Space Complexity: O(1)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
class Solution {
public:
    vector<string> findWords(vector<string>& words) {
        char row0[] = "qwertyuiop";     // size == 10
        char row1[] = "asdfghjkl";      // size == 9
        char row2[] = "zxcvbnm";        // size == 7

        vector<string> result;

        for (vector<string>::iterator it = words.begin(); it != words.end(); it++)
        {
            int flag_row = -1;       // 0: in row0    1: in row1    2: in row2
            int flag_diffrow = 0;    // 0: same row   1: different row
            string str = *it;
            int length = str.size();

            if(length == 1) result.push_back(str);
            else
            {
                char first = str[0];

                // check row0
                for(int i=0; i<10; i++)
                {
                    if(first == row0[i] | (first+32) == row0[i])
                    {
                        flag_row = 0;
                        break;
                    }
                }

                // check row1
                if(flag_row == -1)
                {
                    for(int i=0; i<9; i++)
                    {
                        if(first == row1[i] | (first+32) == row1[i])
                        {
                            flag_row = 1;
                            break;
                        }
                    }
                }

                // check row2
                if(flag_row == -1)
                {
                    for(int i=0; i<7; i++)
                    {
                        if(first == row2[i] | (first+32) == row2[i])
                        {
                            flag_row = 2;
                            break;
                        }
                    }
                }

                switch(flag_row)
                {
                    case 0:

                    // scan str
                    for(int i=1; i<length; i++)
                    {
                        char c = str[i];
                        int flag_in = 0;

                        // check row0
                        for(int j=0; j<10; j++)
                        {
                            if(c == row0[j] | (c+32) == row0[j])
                            {
                                flag_in = 1;
                                break;
                            }
                        }

                        if(flag_in) continue;
                        else
                        {
                            flag_diffrow = 1;
                            break;
                        }
                    }

                    if(flag_diffrow == 0)   result.push_back(str);

                    break;

                    case 1:

                    // scan str
                    for(int i=1; i<length; i++)
                    {
                        char c = str[i];
                        int flag_in = 0;

                        // check row1
                        for(int j=0; j<9; j++)
                        {
                            if(c == row1[j] | (c+32) == row1[j])
                            {
                                flag_in = 1;
                                break;
                            }
                        }

                        if(flag_in) continue;
                        else
                        {
                            flag_diffrow = 1;
                            break;
                        }
                    }

                    if(flag_diffrow == 0)   result.push_back(str);

                    break;

                    case 2:

                    // scan str
                    for(int i=1; i<length; i++)
                    {
                        char c = str[i];
                        int flag_in = 0;

                        // check row2
                        for(int j=0; j<7; j++)
                        {
                            if(c == row2[j] | (c+32) == row2[j])
                            {
                                flag_in = 1;
                                break;
                            }
                        }

                        if(flag_in) continue;
                        else
                        {
                            flag_diffrow = 1;
                            break;
                        }
                    }

                    if(flag_diffrow == 0)   result.push_back(str);

                    break;
                }
            }
        }

        return result;
    }
};

回到 Conquer Leetcode