leetcode500. 键盘行

leetcode

题目描述

给你一个字符串数组 words ，只返回可以使用在 美式键盘 同一行的字母打印出来的单词。键盘如下图所示。

美式键盘 中：

第一行由字符 "qwertyuiop" 组成。 第二行由字符 "asdfghjkl" 组成。 第三行由字符 "zxcvbnm" 组成。

示例 1：

输入：words = ["Hello","Alaska","Dad","Peace"] 输出：["Alaska","Dad"] 示例 2：

输入：words = ["omk"] 输出：[] 示例 3：

输入：words = ["adsdf","sfd"] 输出：["adsdf","sfd"]

提示：

1 <= words.length <= 20 1 <= words[i].length <= 100 words[i] 由英文字母（小写和大写字母）组成

来源：力扣（LeetCode） 链接：https://leetcode.cn/problems/keyboard-row 著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

解题思路

法1

哈希表\

1. 建立一个26位int数组,我们使用哈希表将同一行的元素的值相同,
2. 判断words中的字母是否在同一个行
3. 不在同一行,向下继续索引
4. 储存在同一行的word

• 时间复杂度(O(n))
• 空间复杂度(O(1))

执行结果

法1

func findWords(words []string) []string {
 a := [26]byte{1, 2, 2, 1, 0, 1, 1, 1, 0, 1, 1, 1, 2, 2, 0, 0, 0, 0, 1, 0, 0, 2, 0, 2, 0, 2}//哈希表,分别查找行数
 var t0, tj byte
 t := 0
 for i := 0; i < len(words); i++ {//对每一行进行判断
  if words[i][0] >= 'a' {
   t0 = words[i][0] - 'a'
  } else {
   t0 = words[i][0] - 'A'
  }
  j := 1
  for ; j < len(words[i]); j++ {//判断每个字母是否在同一行
   if words[i][j] >= 'a' {
    tj = words[i][j] - 'a'
   } else {
    tj = words[i][j] - 'A'
   }
   if a[t0] != a[tj] {
    if i < len(words)-1 {
     i++
     if words[i][0] >= 'a' {
      t0 = words[i][0] - 'a'
     } else {
      t0 = words[i][0] - 'A'
     }
     j = 0
    } else {
     break
    }

   }
  }
  if j == len(words[i]) {//都在同一行,储存起来
   words[t] = words[i]
   t++
  }
 }
 return words[:t]
}

执行结果： 通过 显示详情 查看示例代码 添加备注

执行用时： 0 ms , 在所有 Go 提交中击败了 100.00% 的用户 内存消耗： 1.8 MB , 在所有 Go 提交中击败了 94.25% 的用户 通过测试用例： 23 / 23 炫耀一下:

法2

法3