LeetCode_String_17. Letter Combinations of a Phone Number 電話号碼的字母組合（C++）

目錄

1，題目描述

英文描述

中文描述

2，思路

3，AC代碼

4，解題過程

1，題目描述

英文描述

Given a string containing digits from 2-9 inclusive, return all possible letter combinations that the number could represent.

A mapping of digit to letters (just like on the telephone buttons) is given below. Note that 1 does not map to any letters.

Example:

Input: "23"

Output: ["ad", "ae", "af", "bd", "be", "bf", "cd", "ce", "cf"].

Note:

Although the above answer is in lexicographical order, your answer could be in any order you want.

中文描述

給定一個僅包含數字 2-9 的字元串，傳回所有它能表示的字母組合。

給出數字到字母的映射如下（與電話按鍵相同）。注意 1 不對應任何字母。

示例:

輸入："23"

輸出：["ad", "ae", "af", "bd", "be", "bf", "cd", "ce", "cf"].

說明:

盡管上面的答案是按字典序排列的，但是你可以任意選擇答案輸出的順序。

來源：力扣（LeetCode）

連結：https://leetcode-cn.com/problems/letter-combinations-of-a-phone-number

著作權歸領扣網絡所有。商業轉載請聯系官方授權，非商業轉載請注明出處。

2，思路

題目意思比較清楚，相當于全排列，這裡使用DFS遞歸的方法，擷取全部組和：

• 使用深度表示目前周遊到的數字字元；
• 函數中周遊所有數字字元對應的英文字母，并繼續向下搜尋；
• 搜尋出口是：深度depth等于所給字元串的長度，即所有數字字元周遊完畢，這時将目前拼接成的字元串tem添加到ans中；
• 記得彈出字元串最右端的元素，以便獲得其他字元組和；

3，AC代碼

class Solution {
public:
    vector<string> ans;
    unordered_map<char, vector<char>> data;
    void dfs(string digits, int depth, string tem){
        if(depth >= digits.length()){
            ans.push_back(tem);
            return;
        }
        for(auto cha : data[digits[depth]]){    //利用深度depth定位目前周遊的數字
            tem += cha;
            dfs(digits, depth+1, tem);
            tem.pop_back();         // 注意彈出最外層字元
        }
    }
    vector<string> letterCombinations(string digits) {
        if(digits.length() == 0){   //可能出現輸入字元串為空的現象
            return ans;
        }
        data['2'] = {'a', 'b', 'c'};
        data['3'] = {'d', 'e', 'f'};
        data['4'] = {'g', 'h', 'i'};
        data['5'] = {'j', 'k', 'l'};
        data['6'] = {'m', 'n', 'o'};
        data['7'] = {'p', 'q', 'r', 's'};
        data['8'] = {'t', 'u', 'v'};
        data['9'] = {'w', 'x', 'y', 'z'};
        string tem;
        dfs(digits, 0, tem);
        return ans;
    }
};
           

4，解題過程

由于形式比較直接，這裡采用map+DFS的遞歸處理方法，效果還可以