[LeetCode] 17. Letter Combinations of a Phone Number

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.

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