本文主要是介绍LeetCode 面试题 16.20. T9键盘,希望对大家解决编程问题提供一定的参考价值,需要的开发者们随着小编来一起学习吧!
文章目录
- 一、题目
- 二、C# 题解
一、题目
在老式手机上,用户通过数字键盘输入,手机将提供与这些数字相匹配的单词列表。每个数字映射到0至4个字母。给定一个数字序列,实现一个算法来返回匹配单词的列表。你会得到一张含有有效单词的列表。映射如下图所示:
示例 1:
输入: num = “8733”, words = [“tree”, “used”]
输出: [“tree”, “used”]
示例 2:
输入: num = “2”, words = [“a”, “b”, “c”, “d”]
输出: [“a”, “b”, “c”]
提示:
num.length <= 1000
words.length <= 500
words[i].length == num.length
num
中不会出现 0, 1 这两个数字
点击此处跳转题目。
二、C# 题解
题目还好,一个一个匹配就是了。用队列存储中间满足匹配的单词,同时使用 Match 函数判断匹配,而不是建立 Map 判断映射关系,这样会快一点。
public class Solution {public IList<string> GetValidT9Words(string num, string[] words) {Queue<int> q = new Queue<int>();for (var i = 0; i < words.Length; i++) // 将第一个字母匹配的单词进入队列if (Match(num[0], words[i][0]))q.Enqueue(i);for (var i = 1; i < num.Length; i++) { // 在已匹配的单词里面循环匹配int cnt = q.Count;while (cnt-- > 0) {int wi = q.Dequeue();if (Match(num[i], words[wi][i])) q.Enqueue(wi);}}return q.Select(i => words[i]).ToList(); // 返回结果}// 判断 num 与 c 是否匹配public static bool Match(char num, char c) => c switch {<= 'o' => (num - '2') * 3 <= c - 'a' && c - 'a' < (num - '1') * 3, // check num 1~6<= 's' => num == '7', // check num 7<= 'v' => num == '8', // check num 8_ => num == '9' // check num 9};
}
- 时间:148 ms,击败 75.00% 使用 C# 的用户
- 内存:46.18 MB,击败 75.00% 使用 C# 的用户
这篇关于LeetCode 面试题 16.20. T9键盘的文章就介绍到这儿,希望我们推荐的文章对编程师们有所帮助!