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
哈希表\
-
建立一个26位int数组,我们使用哈希表将同一行的元素的值相同, -
判断words中的字母是否在同一个行 -
不在同一行,向下继续索引 -
储存在同一行的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
作者介绍
j
jaryue
V1