LinkedIn 高頻演算法題：手機號數字映射單詞

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，獲得真題。