| leetcode17. 电话号码的字母组合 | 您所在的位置：网站首页 › bd字母组合设计 › leetcode17. 电话号码的字母组合 |
leetcode17. 电话号码的字母组合
|
给定一个仅包含数字2~9的字符串，返回所有它能表示的字母组合。答案可以按任意顺序返回。 给出数字到字母的映射如下（与电话按键相同）。 示例： 输入：digits = “23” 输出：[“ad”, “ae”, “af”, “bd”, “be”, “bf”, “cd”, “ce”, “cf”] 思路： 要说思路的话，思路很简单，人人都能想得到，就是依次取每个数字编号所对应的字符串的字母进行组合，最后便可以得到所有的字母组合。 综上所述，该递归函数应该至少需要四个参数，分别是存储数字编号的字符串digits、标记本次需要使用的数字编号在digits当中的下标 i、当前正在生成的字符串str以及用于存储所有字母组合的vector容器ret。 而题目所给函数只有一个参数，即存储数字编号的字符串digits，所以我们需要设置一个子函数，即递归函数，用于递归进行字母组合。 代码如下： const string str_num[10] = { "", "", "abc", "def", "ghi", "jkl", "mno", "pqrs", "tuv", "wxyz" }; //每个数字编号所对应的字符串 class Solution { public: vector letterCombinations(string digits) { vector ret; //存储所有字母组合 if (digits.empty()) //传入字符串为空，直接返回 return ret; string str; //当前正在进行生成的字符串 int i = 0; //标识本次需要使用的数字编号在digits当中的下标 _letterCombinations(digits, i, str, ret); //递归 return ret; //返回字母组合 } void _letterCombinations(const string& digits, int i, string str, vector& ret) { if (i == digits.size()) //digits当中的数字编号都使用过了 { ret.push_back(str); //将本次的字母组合尾插到ret当中 } else //digits当中的数字编号还有未使用的，当前字符串还未组合完毕 { int num = digits[i] - '0'; //取出digits字符串当中的数字编号 const string& letters = str_num[num]; //数字编号为num所对应的字符串 //使用范围for依次使用字符串letters的每个字符进行组合 for (auto ch : letters) { _letterCombinations(digits, i + 1, str + ch, ret); } } } }; |
注意：1不对应任何字母。
这道题最让人头疼的是代码的设计。 我们可以使用函数递归来解决这个问题，那么这个递归函数需要几个参数呢？
对于每个数字编号所对应的字符串，最好不要设置在所给函数当中或是所给Solution类当中，如果这样设计的话，我们每次调用该函数或是每次实例化一个对象，就需要定义这样一个字符串，而字符串的内容都是一样的，我们没有必要定义多个一样的字符串，因此我们直接将该字符串定义在全局范围即可。【本文地址】
公司简介
联系我们