电话号码的字母组合，C ++解决方案

问题陈述：

您将获得一个从2到9的数字字符串，它们代表电话号码的映射，如下所示。返回所有可能的字母组合。

数字的映射类似于电话号码，如下所示。

下面是示例输入和输出：

Input: "23"

Output: ["ad", "ae", "af", "bd", "be", "bf", "cd", "ce", "cf"].

注意： 输出的顺序可以是任何东西。

我们可以使用诸如迭代，递归，回溯，DFS之类的任何技术来解决此问题。在这里，我们将讨论两种解决方案：迭代方法和回溯方法。

解决方案1：迭代方法

在这种方法中，我们将取3 for循环。我们称它们为：

digits_loop: It will iterate for the length of the digit times. For example, if the input is “23”, it will iterate 2 times. If the input is “234” it will iterate 3 times.

    characters_loop: This is the inner loop for the “digits_loop”. For single digit, it will take the letters for that digit.  It will iterate for the times of letters count for that digit. For example, if the digit is 2, then letters are “abc”, it will iterate for 3 times. If the digit is 9, then the letters are “wxyz”, it will iterate for 4 times.

        combination_loop: It is the inner loop for “characters_loop”. It will iterate for the times of the size of the result set.

注意：由于输入数字为字符串格式，因此不能在for循环中使用。它们需要转换为整数。我们通过使用“ digits [i]– ‘0’ ” formula.

让我们举一个例子并理解它。

输入数字= 23

result_set initially will be of size 1
According to the input, digits_loop will iterate for 2 times

Pass 1 of digits_loop :

	string chars = digit_letter_mapping[digits[i] - '0'];
		chars ="abc"

	characters_loop run for 3 times
		pass 1 of characters_loop
			combination_loop run for 1 time
			temp = a
		
		pass 2 of characters_loop
			combination_loop run for 1 time
			temp = b

		pass 3 of characters_loop
			combination_loop run for 1 time
			temp = b

Pass 2 of digits_loop :

	string chars = digit_letter_mapping[digits[i] - '0'];
		chars ="def"

	characters_loop run for 3 times
		pass 1 of characters_loop
			combination_loop run for 3 time
			pass 1 of characters_loop
				temp = ad
			pass 2 of characters_loop
				temp = bd
			pass 3 of characters_loop
				temp = cd

		
		pass 2 of characters_loop
			combination_loop run for 3 time
			pass 1 of characters_loop
				temp = ae
			pass 2 of characters_loop
				temp = be
			pass 3 of characters_loop
				temp = ce


		pass 3 of characters_loop
			combination_loop run for 3 time
			pass 1 of characters_loop
				temp = af
			pass 2 of characters_loop
				temp = bf
			pass 3 of characters_loop
				temp = cf

C ++中迭代方法的解决方案

#include<iostream>
#include<vector>
using namespace std;

vector<string> letterCombinations(string digits) 
{
    vector<string> res;
    string charmap[10] = {"0", "1", "abc", "def", "ghi", "jkl", "mno", "pqrs", "tuv", "wxyz"};
    res.push_back("");
    for (int i = 0; i < digits.size(); i++)
    {
        vector<string> tempres;
        string chars = charmap[digits[i] - '0'];
        cout<<"chars = "<<chars<<endl;
        cout<<"digits[i] = "<<digits[i]<<endl;
        cout<<"digits[i] - '0' = "<<digits[i] - '0'<<endl;


        for (int c = 0; c < chars.size();c++)
        {
            for (int j = 0; j < res.size();j++)
            {
                cout<<"res[j]= "<<res[j]<<endl;
                cout<<"chars[c]= "<<chars[c]<<endl;
                cout<<"res[j]+chars[c]= "<<res[j]+chars[c]<<endl;


                tempres.push_back(res[j]+chars[c]);
            }
            cout<<"==============="<<endl;
        }
        res = tempres;
    }
    return res;
}

int main()
{
    string digits = "23";
     vector<string> res = letterCombinations(digits);

    for (auto &i : res) 
    {
            for (auto &j : i)
                cout << j;
            cout << ' ';
    }
        cout << endl;
}
    

输出：

ad bd cd ae be ce af bf cf

回溯方法：

有关回溯的介绍，请阅读我写的以下文章。

//www.dy0519.cn/given-an-array-of-non-repeating-numbers-and-a-key-find-all-the-unique-combinations-in-that-array-where-the-sum-of-those-combination-is-equal-to-the-key/

使用回溯方法，解决方案非常简单。

解决方案基于以下事实：如果字母组合的长度等于数字的长度，我们将其写入最终结果集中。

例：

Input: "23"
Output: ["ad", "ae", "af", "bd", "be", "bf", "cd", "ce", "cf"].

Input: 234
Output: adg bdg cdg aeg beg ceg afg bfg cfg adh bdh cdh aeh beh ceh afh bfh cfh adi bdi cdi aei bei cei afi bfi cfi

如您所见，输出组合的长度等于数字的长度。

因此，我们将递归调用“ get_combination_backtrack”函数，如果组合字符串的长度等于数字的长度，则应将其推入最终结果集中。

回溯功能“ get_combination_backtrack”具有5个参数：

1. 字母和数字的映射
2. 最终结果集
3. 用于存储中间结果的局部变量
4. 起始索引
5. 输入数字

C ++中回溯的解决方案

#include<iostream>
#include<vector>
using namespace std;



void get_combination_backtrack( string digits_letter_combination_map[], vector<string>& final_result_set, string& local_storage, int index, string& digits) 
{
        if(index==digits.size())
            final_result_set.push_back(local_storage);
        else
            for(int i=0;i<digits_letter_combination_map[digits[index]-'0'].size();i++) 
            {
                local_storage.push_back(digits_letter_combination_map[digits[index]-'0'][i]);
                get_combination_backtrack(digits_letter_combination_map, final_result_set, local_storage, index+1, digits);
                local_storage.pop_back();
            }
}


vector<string> getLetterCombination(string digits) 
{
	vector<string> final_result_set;
    string digits_letter_combination_map [10] = {"0", "1", "abc", "def", "ghi", "jkl", "mno", "pqrs", "tuv", "wxyz"};
    string local_storage;

    get_combination_backtrack(digits_letter_combination_map, final_result_set,local_storage, 0, digits);

    return final_result_set;
}



int main()
{
    string digits = "23";
    vector<string> final_result = getLetterCombination(digits);

    for (int i = 0; i < final_result.size(); i++)
                cout << final_result[i] << " ";
    cout<<endl;

}

输出：

ad bd cd ae be ce af bf cf

该网站上可用的教程列表：