一、题目描述
给你一个字符串数组 w o r d s words words,只返回可以使用在美式键盘同一行的字母打印出来的单词。键盘如下图所示:
美式键盘中:
- 第一行由字符 “ q w e r t y u i o p ” “qwertyuiop” “qwertyuiop”组成。
- 第二行由字符 “ a s d f g h j k l ” “asdfghjkl” “asdfghjkl”组成。
- 第三行由字符 “ z x c v b n m ” “zxcvbnm” “zxcvbnm”组成。
二、示例
输入: words = [“Hello”, “Alaska”, “Dad”, “Peace”]
输出: [“Alaska”, “Dad”]
三、主体思路
解决该题的关键就是建立每个字母与其所在行号的映射关系,当关系建立后我们就可以对所给的字符串进行遍历,如果一个字符串中的所有字符都对应在键盘当中的同一行,则该字符串满足要求,否则不满足要求,我们只需选出满足要求的字符串进行返回即可。
我们既可以选择直接使用C++STL库当中现有的关联式容器,也可以选择自己设计一个哈希函数,该哈希函数需要通过字母的ASCII码值找到其对应行号,下面我们分别用这两种方法对该题目进行刨析。
四、代码实现
1、利用关联式容器建立映射
C++当中的常用的关联式容器有map/set和unordered_map/unordered_set,我们一般情况下优先使用unordered系列的容器,原因在博主的另一篇博客当中有说明。
我们可以选择用三个unordered_set容器,分别存储第一行字母、第二行字母和第三行字母。当我们需要判断一个字符串当中的字符是否全部出现在同一行时,只需判断该字符串中的所有字符能否在同一个unordered_set容器当中找到即可,如果能则满足题目要求,否则不满足题目要求。
但实际上用不着建立三张哈希表,我们可以直接使用一个unordered_map容器,该容器当中存储的就是每个字母与其所在行号的映射关系,此时我们也能够通过字母找到其对应的行号,进而判断字符串是否满足题目要求。
代码如下:
当然,如果你对C++STL库当中容器的使用足够熟练,你可以将建立三行字母映射关系的代码合并在一起。
代码如下:
说明一下:
- 代码中将 “ q w e r t y u i o p ” “qwertyuiop” “qwertyuiop”所在的行叫做第0行, “ a s d f g h j k l ” “asdfghjkl” “asdfghjkl”所在的行叫做第1行, “ z x c v b n m ” “zxcvbnm” “zxcvbnm”所在的行叫做第2行。
2、直接定址法建立映射
还记得“统计字符串中每个字符出现的次数”这个题目吗,这是一个经典的哈希映射题目,由于26个字母的ASCII码值是连续的,每个小写字母的ASCII码值减去字符 a a a的ASCII码值后就能对应映射到0~25。
因此这里我们可以建立一个字符串 t a b l e table table,该字符串中有26个字符,字符的下标就是从0到25,依次对应的就是每个字母所在键盘当中的行号。当我们需要查找某个字母对应所在的行号时,先将该字母的ASCII码值减去字符 a a a的ASCII码值得到一个差值,此时在 t a l b e talbe talbe当中以该差值为下标的字符就是该字符所在的行号。
代码如下:
说明一下:
- 代码中将 “ q w e r t y u i o p ” “qwertyuiop” “qwertyuiop”所在的行叫做第0行, “ a s d f g h j k l ” “asdfghjkl” “asdfghjkl”所在的行叫做第1行, “ z x c v b n m ” “zxcvbnm” “zxcvbnm”所在的行叫做第2行。
- 我们只建立了小写字母与其对应行号的映射关系,大写字母可以先转换成小写字母后再进行查找。