LinkedIn 高频算法题：手机号数字映射单词（Phone Keypad Word Mapping）

# 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']

高效思路：单词反向编码

相比生成所有组合（指数级），更实用的做法是：

1. 建立字母 -> 数字映射表
2. 把每个已知单词编码成数字串 code(word)
3. 对输入号码，只要匹配 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，获得真题。