题目链接：Letter Combinations of a Phone Number

Given a digit string, 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.

1       2(abc)  3(def) 
4(ghi)  5(jkl)  6(mno) 
7(pqrs) 8(tuv)  9(wxyz) 
*       0       #

For example:

Input:Digit string "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.

这道题的要求是给定一个数字字符串，返回手机键盘上对应的所有可能的字母组合。其中返回的顺序可以是任意的。

这道题的思路比较简单，可以迭代，即依次读取字符串中的每位数字，然后把数字对应的字母依次加到当前的所有结果中，然后进入下一次迭代。也可以用递归来解，思路也类似，就是对于当前已有的字符串，递归剩下的数字串，然后得到结果后加上去。假设输入字符串总共有n个数字，平均每个数字可以代表m个字符，那么时间复杂度是O(m^n)，确切点是输入字符串中每个数字对应字母数量的乘积，即结果的数量，空间复杂度也是一样。

时间复杂度：O(m^n)

空间复杂度：O(m^n)

  1. 迭代

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18

class Solution
{
public:
    vector<string> letterCombinations(string digits) // 迭代
    {
        string d[] = {"", "", "abc", "def", "ghi", "jkl", "mno", "pqrs", "tuv", "wxyz"}, s="";
        vector<string> v({""});
        for(int i = 0; i < digits.size(); ++ i)
        {
            vector<string> temp;
            for(int j = 0; j < v.size(); ++ j)
                for(int k = 0; k < d[digits[i] - '0'].size(); ++ k)
                    temp.push_back(v[j] + d[digits[i] - '0'][k]);
            v = temp;
        }
        return v;
    }
};

  1. 递归

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20

class Solution
{
private:
    vector<string> v;
    void letterCombinations(string digits, int b, string s, string d[])
    {
        if(digits.size() == b)
            v.push_back(s);
        else
            for(int i = 0; i < d[digits[b] - '0'].size(); ++ i)
                letterCombinations(digits, b + 1, s + d[digits[b] - '0'][i], d);
    }
public:
    vector<string> letterCombinations(string digits) // 递归
    {
        string d[] = {"", "", "abc", "def", "ghi", "jkl", "mno", "pqrs", "tuv", "wxyz"}, s="";
        letterCombinations(digits, 0, s, d);
        return v;
    }
};