17. Letter Combinations of a Phone Number

题目链接：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)，确切点是输入字符串中每个数字对应字母数量的乘积，即结果的数量和空间的复杂性。

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;     } };

// Recursionclass Solution {public:    vector<string> letterCombinations(string digits) {        vector<string> res;        if (digits.empty()) return res;        string dict[] = {"abc", "def", "ghi", "jkl", "mno", "pqrs", "tuv", "wxyz"};        letterCombinationsDFS(digits, dict, 0, "", res);        return res;    }    void letterCombinationsDFS(string digits, string dict[], int level, string out, vector<string> &res) {        if (level == digits.size()) res.push_back(out);        else {            string str = dict[digits[level] - '2'];            for (int i = 0; i < str.size(); ++i) {                out.push_back(str[i]);                letterCombinationsDFS(digits, dict, level + 1, out, res);                out.pop_back();            }        }    }};

#include <iostream>#include <vector>using namespace std;#define __tmain mainclass Solution{public:    void dfsgetString(string digits,                      int index,                      string curr,                      vector<string> dict,                      vector<string> *result)    {        if(index == digits.size())        {            //cout <<"解" <<curr <<endl;            result->push_back(curr);            return ;        }        char strChar = digits[index];        //cout <<“当前数字” <<strChar <<endl;        // 循环当前数字对应的每个字符        for(int i = 0; i < dict[strChar - '0'].size(); i++)        {            string temp = curr;            curr += dict[strChar-'0'][i];            //cout <<"取出" <<dict[strChar-'0'][i] <<endl;            //cout <<"得到" <<curr <<endl;            dfsgetString(digits, index + 1, curr, dict, result);            //  每次递归退出后，恢复原来的现场，            //  回复curr的值主要是回复            //cout <<digits <<", " <<index <<", " <<curr <<endl;            curr = temp;        }    }    vector<string> letterCombinations(string digits)    {        vector<string> res;        if(digits == "")        {            return res;        }        vector<string> dict(10);        dict[2] = "abc";        dict[3] = "def";        dict[4] = "ghi";        dict[5] = "jkl";        dict[6] = "mno";        dict[7] = "pqrs";        dict[8] = "tuv";        dict[9] = "wxyz";        string curr ="\0";        dfsgetString(digits, 0, curr, dict, &res);        return res;    }};int __tmain(void){    string digits = "23";    Solution solu;    vector<string> res = solu.letterCombinations(digits);    for(int i = 0; i < res.size( ); i++)    {        std::cout <<res[i] <<endl;    }    return 0;}

class Solution {public:    vector<string> letterCombinations(string digits)     {        vector<string> res;        if(digits.size()==0) return res;        string local;        vector<vector<char>> table(2,vector<char>());        table.push_back(vector<char>{'a','b','c'}); // index 2        table.push_back(vector<char>{'d','e','f'}); // 3        table.push_back(vector<char>{'g','h','i'});        table.push_back(vector<char>{'j','k','l'}); // 5        table.push_back(vector<char>{'m','n','o'});        table.push_back(vector<char>{'p','q','r','s'}); // 7        table.push_back(vector<char>{'t','u','v'});        table.push_back(vector<char>{'w','x','y','z'}); // 9        backtracking(table,res,local,0,digits);        return res;    }    void backtracking(const vector<vector<char>>& table, vector<string>& res, string& local, int index, const string& digits) {        if(index==digits.size())            res.push_back(local);        else            for(int i=0;i<table[digits[index]-'0'].size();i++) {                local.push_back(table[digits[index]-'0'][i]);                backtracking(table, res, local, index+1, digits);                local.pop_back();            }    }};