LeetCode-Daily-Question-34

Jul 21st 2022

7 月 21 日 每日一题

17. Letter Combinations of a Phone Number

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.

1
2
Input: digits = "23"
Output: ["ad","ae","af","bd","be","bf","cd","ce","cf"]

思路

Using bsf (a queue) or a temp vector to store the intermediate status of the combinations.

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
class Solution {
public:
    vector<string> letterCombinations(string digits) {
        if(digits.empty())
            return {};
        vector<string> phone = {"0", "1", "abc", "def", "ghi", "jkl", "mno", "pqrs", "tuv", "wxyz"};
        queue<string> bsf;
        vector<string> ans;
        bsf.push("");
        while(!bsf.empty()){
            string s = bsf.front();
            bsf.pop();
            if(s.length() == digits.length())
                ans.push_back(s);
            else{
                for(char c: phone[digits[s.length()] - '0'])
                    bsf.push(s + c);
            }
        }
        return ans;
    }

};
,
  1. 7 月 21 日 每日一题
    1. 17. Letter Combinations of a Phone Number
    2. 思路
    3. 代码