17.电话号码的字母组合

题目
给定一个仅包含数字 2-9 的字符串，返回所有它能表示的字母组合。

给出数字到字母的映射如下（与电话按键相同）。注意 1 不对应任何字母。

示例:

输入："23"
输出：["ad", "ae", "af", "bd", "be", "bf", "cd", "ce", "cf"].
说明:
尽管上面的答案是按字典序排列的，但是你可以任意选择答案输出的顺序。

思路:**
1、第一次写的时候误解题意，误以为2本身可以组合ab ac bc ，但是发现并这样组合。利用了map查表法搜索。

#include <string>
#include <vector>
#include <map>
using namespace std;
class Solution {
public:
    /*第一次写的时候误解题意，2本身可以组合ab ac bc ，但是发现并不是。。。
     * 第二次改只需把for循环放入遍历里边即可
     */
    vector<string> letterCombinations(string digits) {
        vector<string> resultStr;
        map<char, vector<string>> numStr{ {'2', {"a","b","c"}},{ '3',{ "d","e","f" } } ,
            { '4',{ "g","h","i" } } ,{ '5',{ "j","k","l" } } ,{ '6',{ "m","n","o" } }
           ,{ '7',{ "p","q","r", "s"} } ,{ '8',{ "t","u","v" } } ,{ '9',{ "w","x","y", "z"} } };
        map<char, vector<string>>::iterator iter;
        vector<string> jihe;
        if (digits.size() == 1)
        {
            for (char eve : digits)
            {
                return resultStr = numStr.find(eve)->second;
            }
            
        }
        for (char eve : digits)
        {
            iter = numStr.find(eve);
            int size = iter->second.size();
            for (int i = 0; i < size; i ++)
            {
                string a = iter->second.at(i);
                jihe.push_back(a);
            }
        }
        for (int i = 0; i < jihe.size(); i ++)
        {
            for (int j = i + 1; j < jihe.size();  ++j)
            {
            //  string str = (std::to_string(char(jihe[i])) + std::to_string(char(jihe[j])));
                string str = (jihe[i] +jihe[j] );
                resultStr.push_back(str) ;
            }
        }
        return resultStr;
    }
};
int main(int argc, char* argv[])
{
    string str = "23";
    vector<string> res = Solution().letterCombinations(str);
    system("pause");
}

2.把第一次中的代码第二个for循环放入遍历中即可删除自身项。

    vector<string> letterCombinations(string digits) {
        vector<string> resultStr;
        map<char, vector<string>> numStr{ {'2', {"a","b","c"}},{ '3',{ "d","e","f" } } ,
            { '4',{ "g","h","i" } } ,{ '5',{ "j","k","l" } } ,{ '6',{ "m","n","o" } }
           ,{ '7',{ "p","q","r", "s"} } ,{ '8',{ "t","u","v" } } ,{ '9',{ "w","x","y", "z"} } };
        map<char, vector<string>>::iterator iter;
        vector<string> jihe;
        if (digits.size() == 1)
        {
            for (char eve : digits)
            {
                return resultStr = numStr.find(eve)->second;
            }
            
        }
        for (char eve : digits)
        {
            iter = numStr.find(eve);
            int size = iter->second.size();
            for (int i = 0; i < size; i ++)
            {
                string a = iter->second.at(i);
                jihe.push_back(a);
            }
            for (int i = 0; i < size; i++)
            {
                for (int j =  size; j < jihe.size(); ++j)
                {
                    //  string str = (std::to_string(char(jihe[i])) + std::to_string(char(jihe[j])));
                    string str = (jihe[i] + jihe[j]);
                    resultStr.push_back(str);
                }
            }
        }
        return resultStr;
    }
};

3.但是这样做仍然无法满足题意，未考虑两个以上字符的情况。考虑到电话号码的长度是任意的，因此决定利用递归方法。

/**全局变量**/
string phoneNum[] = { "", "", "abc", "def" ,"ghi", "jkl", "mno", "pqrs","tuv", "wxyz" };
    vector<string> letterCombinations2(string digits)
    {
        vector<string> resultStr;
        string ss = "";
        findStr(resultStr, digits, 0, ss);
        return resultStr;
        
    }
    void findStr(vector<string> &resultStr, string &digits, int index, string &ss)
    {
        if (index == digits.size()) {
            resultStr.push_back(ss);
            return;
        }
        for (int i = 0 ; i < phoneNum[digits[index] - '0'].size(); i ++)
        {
            ss = ss + phoneNum[digits[index] - '0'][i];
            findStr(resultStr, digits, index + 1, ss);
            ss.pop_back();
        }
    }