j

jaryue

V1

2023/04/16阅读:24主题:默认主题

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{12210111011122000010020202}//哈希表,分别查找行数
 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


分类:

后端

标签:

后端

作者介绍

j
jaryue
V1