链接直达

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. 分析

核心思路：

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
}