[LeetCode] 17. Letter Combinations of a Phone Number

题目

Letter Combinations of a Phone Number

描述

给定一个由电话号码上面的数字组成的字符串，返回由这些数字所能组成的字母组合。

每个数字所能代表的字母集如下：

0   ""
1   ""
2   "abc"
3   "def"
4   "ghi"
5   "jkl"
6   "mno"
7   "pqrs"
8   "tuv"
9   "wxyz"

示例

输入："23"
输出：["ad", "ae", "af", "bd", "be", "bf", "cd", "ce", "cf"]

要求

不要求返回结果数组一定按字母顺序出现。

思路

可以采用回溯的办法，但用递归的话可能会比较简单，更容易理解。

代码

class Solution {
    void combine(vector<string>& result, const string& digits, size_t i, const string& prefix)
    {
        static map<char, string> d2l {
            {0, ""},
            {1, ""},
            {2, "abc"},
            {3, "def"},
            {4, "ghi"},
            {5, "jkl"},
            {6, "mno"},
            {7, "pqrs"},
            {8, "tuv"},
            {9, "wxyz"},
        };

        if(i >= digits.size()) {
            result.emplace_back(prefix);
            return;
        }
        else {
            for(const auto& ch : d2l[digits[i]-'0']) {
                combine(result, digits, i + 1, prefix + ch);
            }
        }
    }

public:
    vector<string> letterCombinations(string digits) {
        vector<string> result;
        if(!digits.empty()) {
            combine(result, digits, 0, "");
        }
        return move(result);
    }
};