C++:电话号码的字符组合

题目描述

给定一个仅包含数字 2-9 的字符串，返回所有它能表示的字母组合。答案可以按任意顺序返回。

给出数字到字母的映射如下（与电话按键相同）。注意 1 不对应任何字母。
在这里插入图片描述

示例 1：

输入：digits = "23"
输出：["ad","ae","af","bd","be","bf","cd","ce","cf"]
示例 2：

输入：digits = ""
输出：[]
示例 3：

输入：digits = "2"
输出：["a","b","c"]

分析

本题可以考虑采用进制的思想来进行处理，首先计算出所有可能的组合数目，然后从0开始变量，每一个对应下标都对应着一种组合方式，只需根据对应的三进制或者四进制反解出该位的字符即可
如 “23”
对应的1-9种组合，分别用两个三进制表示就是00 01 02 10 11 12 20 21 22
而“27”
则可以用三进制与四进制混合来表示，每个字符对应进制取决于这个数字对应的字符个数
“27”共对应12种组合，用三进制混合四进制表示就是
00 01 02 03 10 11 12 13 20 21 22 23

实现

#include <iostream>
#include <vector>
#include <unordered_map>
#include <string>
using namespace std;
//字符组合  按照拼音九键的编码方式 输入0-9组成的字符串  各选择每个数组对应字符串的一个字符  返回所有可能的组合 
//如 “23”  返回["ad","ae","af","bd","be","bf","cd","ce","cf"]
vector<string> letterCombinations(string &digits);
int main()
{
    string digits = "27";
    letterCombinations(digits);
    system("pause");
    return 0;
} 

vector<string> letterCombinations(string& digits)
{
    vector<string> ans;
    vector<string> map = {"", "", "abc", "def", "ghi", "jkl", "mno", "pqrs", "tuv", "wxyz"};
    int num = 1;
    //计算所有可能
    for(int i=0;i<digits.size();i++)
        num *= map[digits[i] - '0'].size();
    //根据下标反解每一位对应的字符
    for (int i = 0; i < num;i++)
    {
        string str;
        int cnt = num;
        int temp_i = i;
        for (int j = 0; j < digits.size(); j++)
        {
            temp_i %= cnt;
            cnt/=map[digits[j] - '0'].size();
            str.push_back(map[digits[j] - '0'][temp_i / cnt]);
        }
        ans.push_back(str);
    }
    return ans;
}