【LeetCode & 剑指offer刷题】回溯法与暴力枚举法题5：Letter Combinations of a Phone Number

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.

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.

C++

//传统手机数字盘的按键产生的所有可能字母组合
//感觉和回溯法没有什么关系，就是穷举法
class Solution
{
public:
    vector<string> letterCombinations(string digits)
    {
        if(digits.empty()) return vector<string>(); //异常情况处理
       
        unordered_map<char,string> map =
        {
            {'2',"abc"},
            {'3', "def"},
            {'4', "ghi"},
            {'5', "jkl"},
            {'6', "mno"},
            {'7', "pqrs"},
            {'8',"tuv"},
            {'9',"wxyz"}
        };
       
        vector<string> result;
        result.push_back(""); // add a seed for the initial case,因为之后会遍历结果向量 push了一个空元素，result size变为1
        for(int i = 0; i<digits.size(); i++)//遍历数字, 如 2 3
        {
            if(map.find(digits[i]) == map.end()) continue;//如果不是2~9的数字，继续循环
           
            string& candidate = map[digits[i]]; //得到候选字符构成的字符串
            vector<string> temp;
            for(string& ri:result) //遍历结果向量，如 "a" "b" "c" 
            {
               for(char ci:candidate) //遍历候选字符 如 "def"
               {
                   temp.push_back(ri+ci);
               }
            }
           // result = temp; //复制到结果向量
            result.swap(temp); //交换，swap does not take memory copy
        }
        return result;
    }
};