USACO 1.2 Name That Number：字母電話號碼映射查找

USACO 1.2 Name That Number

經典 AD-hoc 題：給定數字串（2-9），按電話鍵盤映射（2:ABC, 3:DEF, 4:GHI, 5:JKL, 6:MNO, 7:PRS, 8:TUV, 9:WXY），從字典中找出映射後與輸入數字完全匹配的單詞。注意 Q 和 Z 無映射。

問題分析

• 字典最多 5000 個單詞，長度 ≤12，總操作 6×10^4，極小。
• 預處理：將字典每個單詞轉換為對應數字串（跳過 Q/Z）。
• 查詢：直接比對數字串，輸出匹配的原單詞；無匹配輸出 NONE。

映射表

int map[26] = {
    2,2,2, 3,3,3, 4,4,4, 5,5,5, 6,6,6, 7,0,7,7, 8,8,8, 9,9,9, 0
    // A B C  D E F  G H I  J K L  M N O  P Q R S  T U V  W X Y  Z
};
// Q 和 Z 映射為 0（無效），遇到跳過

代碼實現（C++）

> word) {
        if(word[0] == 'Z') break; // 字典結束標記
        dict.push_back(word);
    }
    
    string target; fin >> target;
    int map[26] = {2,2,2,3,3,3,4,4,4,5,5,5,6,6,6,7,0,7,7,8,8,8,9,9,9,0};
    
    bool found = false;
    for(string& w : dict) {
        string num = "";
        for(char c : w) {
            int m = map[c - 'A'];
            if(m == 0) { num = ""; break; } // 含 Q/Z 無效
            num += char('0' + m);
        }
        if(num == target) {
            fout << w << '\n';
            found = true;
        }
    }
    if(!found) fout << "NONE\n";
    return 0;
}

關鍵點

• 字典讀取到 'Z' 開頭單詞結束。
• 單詞中出現 Q 或 Z 直接判定無效（不匹配任何數字）。
• 數字串可能很長（12 位），用 string 避免整型溢出。

複雜度

預處理 O(總字符數)，查詢 O(字典大小 × 單詞長度)，完全在限制內。

總結

本題考察字符串映射與字典查找，預處理+線性掃描即可，無需複雜數據結構。注意 Q/Z 的特殊處理和字典結束標記。