# LinkedIn 高频算法题：手机号数字映射单词（Phone Keypad Word Mapping）
oavoservice 原创复盘：核心不是暴力枚举所有字母组合，而是把已知词表反向映射成数字模式。
题目（改写版）
给定电话键盘映射（2->abc, 3->def, ..., 9->wxyz），以及一个已知词表 KNOWN_WORDS。
对输入手机号 phoneNumber，输出所有可以由该号码映射得到的单词（必须在 KNOWN_WORDS 中）。
示例（改写自常见题型）：
KNOWN_WORDS = ['careers', 'linkedin', 'hiring', 'interview', 'linkedgo']phoneNumber = 2273377输出['careers']phoneNumber = 54653346输出['linkedin', 'linkedgo']
高效思路：单词反向编码
相比生成所有组合（指数级），更实用的做法是：
- 建立字母 -> 数字映射表
- 把每个已知单词编码成数字串
code(word) - 对输入号码，只要匹配
code(word) == phoneNumber即可
这样复杂度大约是：O(total_chars_in_dict + candidates)。
Python 实现
from typing import List, Dict
def build_char_to_digit() -> Dict[str, str]:
mapping = {
'2': 'abc',
'3': 'def',
'4': 'ghi',
'5': 'jkl',
'6': 'mno',
'7': 'pqrs',
'8': 'tuv',
'9': 'wxyz',
}
char_to_digit = {}
for d, letters in mapping.items():
for ch in letters:
char_to_digit[ch] = d
return char_to_digit
def word_to_digits(word: str, char_to_digit: Dict[str, str]) -> str | None:
out = []
for ch in word.lower():
if ch not in char_to_digit:
return None
out.append(char_to_digit[ch])
return "".join(out)
def phone_keypad_word_mapping(phone: str, known_words: List[str]) -> List[str]:
char_to_digit = build_char_to_digit()
res = []
for w in known_words:
code = word_to_digits(w, char_to_digit)
if code == phone:
res.append(w)
return res
进阶优化（面试加分）
- 多次查询：预处理
digits -> [words]的哈希表，查询变成O(1)。 - 前缀匹配/分词：如果题目允许手机号分段拼多个单词，可以用 Trie + DFS 或 DP。
这类题在 LinkedIn 很常见，因为它把“产品场景（搜索/输入法）”和“算法优化”结合起来。oavoservice 训练重点是：先给出可运行的 baseline，再讲清楚为什么要反向映射。
需要面试真题？ 立刻联系微信 Coding0201，获得真题。
联系方式
Email: [email protected] Telegram: @OAVOProxy