17. Letter Combinations of a Phone Number

  • Hardness: \(\color{orange}\textsf{Medium}\)
  • Ralated Topics: Hash Table,String,Backtracking

一、題目

Given a string containing digits from 2-9 inclusive, return all possible letter combinations that the number could represent. Return the answer in any order
A mapping of digits to letters (just like on the telephone buttons) is given below. Note that 1 does not map to any letters.
1200px-telephone-keypad2svg

Example 1:

  • Input: digits = “23”
  • Output: [“ad”,“ae”,“af”,“bd”,“be”,“bf”,“cd”,“ce”,“cf”]

Example 2:

  • Input: ""
  • Output: []

Example 3:

  • Input: “2”
  • Output: [“a”,“b”,“c”]

Constraints:

  • 0 <= digits.length <= 4
  • digits[i] is a digit in the range ['2', '9'].

二、分析

  • DFS 演算法是在遍歷「節點」，而回溯法是在遍歷「樹枝」。站在一個節點上，需思考三個問題：
    1. 路徑(PATH)：已做出的選擇。
    2. 選項(OPTION)：當前可以做的選擇。
    3. 終止條件(TERMINATE)：到達決策樹的底層，無法再做其它選擇。
    • 以下為回溯法的框架：
    vector<PATH> res;
void backtrack(PATH, OPTION) {
    if (TERMINATE) {
        res.push_back(PATH);
        return;
    }
    for (CHOICE : OPTION) {
        DO OPTION;
        backtrack(PATH, OPTION);
        CANCEL OPTION;
    }
}

三、解題

1. Backtracking

  • Time complexity: \(O(m\times n)，\text{m }為\text{ digits }的長度，\text{n }為\text{ dict[i] }的長度\)，
  • Space complexity: \(O(m\times n)\)
vector<string> letterCombinations(string digits) {
    vector<string> dict = {"", "", "abc", "def", "ghi", "jkl", "mno", "pqrs", "tuv", "wxyz"};   // 選項
    vector<string> res;
    if (digits.empty()) return res;
    string path;        // 路徑
    backtrack(dict, res, path, digits);
    return res;
}
void backtrack(vector<string> dict, vector<string>& res, string& path, string& digits) {
    if (path.length() == digits.length()) {     // 終止條件
        res.push_back(path);                    // 記錄路徑
        return;
    }
    int i = path.size();
    string letters = dict[digits[i] - '0'];
    for (char letter : letters) {
        path.push_back(letter);               // 做選擇
        backtrack(dict, res, path, digits);
        path.pop_back();                      // 撤銷選擇
    }
}

回目錄 Catalog