1. 题目描述
在老式手机上,用户通过数字键盘输入,手机将提供与这些数字相匹配的单词列表。每个数字映射到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 这两个数字
2. 分析
核心思路:
哈希表
前缀树
3. 代码
3.1. 哈希表
var table = [26]byte{
'2', '2', '2', // a, b, c
'3', '3', '3', // d, e, f
'4', '4', '4', // g, h, i
'5', '5', '5', // j, k, l
'6', '6', '6', // m, n, o
'7', '7', '7', '7', // p, q, r, s
'8', '8', '8', // t, u, v
'9', '9', '9', '9', // w, x, y, z
}
func getValidT9Words(num string, words []string) []string {
ans := make([]string, 0, len(words))
out:
for _, word := range words {
for i := range word {
if table[word[i]-'a'] != num[i] {
continue out
}
}
// 全匹配,更新答案
ans = append(ans, word)
}
return ans
}
3.2. 前缀树
var table = [10]string{
"", "",
"abc",
"def",
"ghi",
"jkl",
"mno",
"pqrs",
"tuv",
"wxyz",
}
type Trie struct {
child [26]*Trie
origin string
}
func (t *Trie) Push(word, origin string) {
if len(word) == 0 {
return
}
k := word[0] - 'a'
if t.child[k] == nil {
t.child[k] = &Trie{}
}
t.child[k].origin = origin
t.child[k].Push(word[1:], origin)
}
func getValidT9Words(num string, words []string) []string {
if len(num) == 0 {
return nil
}
t := &Trie{}
for _, word := range words {
t.Push(word, word)
}
// 按照num序列做广搜
queue := list.New()
k := num[0] - '0'
for i := range table[k] {
start := table[k][i] - 'a'
if t.child[start] != nil {
queue.PushBack(t.child[start])
}
}
for i := 1; i < len(num); i++ {
k := num[i] - '0'
if queue.Len() == 0 {
return nil
}
newQueue := list.New()
for e := queue.Front(); e != nil; e = e.Next() {
ct := e.Value.(*Trie)
for i := range table[k] {
start := table[k][i] - 'a'
if ct.child[start] != nil {
newQueue.PushBack(ct.child[start])
}
}
}
queue = newQueue
}
ans := make([]string, 0, queue.Len())
for e := queue.Front(); e != nil; e = e.Next() {
ans = append(ans, e.Value.(*Trie).origin)
}
return ans
}
评论