【LeetCode】17. Letter Combinations of a Phone Number 解題報告

撰寫於2022-07-06閱讀次數

17. Letter Combinations of a Phone Number / Medium

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: digits = “”
Output: []

Example 3:

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

Constraints:

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

Solution: Backtracking

思路

效能

Complexity

  • Time Complexity: O(N*4^N), where N is the length of digits, and 4 is the maximum value length in the hash map
  • Space Complexity: O(N), the space occupied by the recursion call stack will only go as deep as the number of digits in the input.

LeetCode Result

Code

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
class Solution {
public:
    vector<string> letterCombinations(string digits) {
        if(digits.empty()) return {};
        combination(digits, "");
        return output;
    }
    
    void combination(string nowDigits, string nowCombination) {
        if(nowDigits.empty()) {
            output.emplace_back(nowCombination);
            return;
        }
        string charCandidate = hmap[nowDigits[0]];
        for(const auto& cans: charCandidate) {
            nowCombination += cans;
            combination(string(nowDigits.begin()+1, nowDigits.end()), nowCombination);
            nowCombination.pop_back();
        }
    }
private:
    vector<string> output;
    unordered_map<char, string> hmap = {
        {'2', "abc"},
        {'3', "def"},
        {'4', "ghi"},
        {'5', "jkl"},
        {'6', "mno"},
        {'7', "pqrs"},
        {'8', "tuv"},
        {'9', "wxyz"},
    };   
};