【算法与数据结构】17、LeetCode电话号码的字母组合

组合"/>

【算法与数据结构】17、LeetCode电话号码的字母组合

文章目录

• 一、题目
• 二、解法
• 三、完整代码

所有的LeetCode题解索引，可以看这篇文章——【算法和数据结构】LeetCode题解。

一、题目

二、解法

  思路分析：本题需要解决的问题有三个：

• 一、如何实现数字到字母的映射
• 二、如何实现组合问题
• 三、如何解决1 *等异常情况
    数字到字母的映射有两种，一种是寻找数字和字母之间的函数关系，但这种关系并不好找，2-6分别映射了三个字母，7 9 映射了四个字母，函数关系并不明显，因此我们直接建立一个数字到字母的映射map。

const string letterMap[10] = {"", // 0"", // 1"abc", // 2"def", // 3"ghi", // 4"jkl", // 5"mno", // 6"pqrs", // 7"tuv", // 8"wxyz" // 9
};

  第二个组合问题可以参考【算法与数据结构】77、LeetCode组合，稍做修改， 程序当中index来表示当前递归正在处理的数字的索引，终止条件为处理的索引=digits大小。同时利用ASCII码直接减去‘0’得到对应的数字，并且做了异常值的处理，大于‘9’小于‘0’就是异常值。
  程序如下：

class Solution {
private:vector<string> result;     // 结果合集string path;void backtracking(const string& digits, int index) {    // index表示当前处理的数字索引if (index == digits.size()) {   // 终止条件result.push_back(path);return;}if (digits[index] > '9' || digits[index] < '0') {   // 异常处理result.clear();result.push_back("input_error");return;}else {int digit = digits[index] - '0';string letter = letterMap[digit];for (int i = 0; i < letter.size(); i++) { // 剪枝优化          path += letter[i];  // 处理节点backtracking(digits, index + 1);  // 递归path.pop_back();    // 回溯，撤销处理的节点}}}
public:const string letterMap[10] = {"", // 0"", // 1"abc", // 2"def", // 3"ghi", // 4"jkl", // 5"mno", // 6"pqrs", // 7"tuv", // 8"wxyz" // 9};vector<string> letterCombinations(string digits) {if(digits.size()) backtracking(digits, 0);           return result;}
};

复杂度分析：

• 时间复杂度： O ( 3 m ∗ 4 n ) O(3^m*4^n) O(3m∗4n), m为映射有三个字母的数字个数，n为映射有四个字母的数字个数。
• 空间复杂度： O ( 3 m ∗ 4 n ) O(3^m*4^n) O(3m∗4n)。

三、完整代码

# include <iostream>
# include <vector>
# include <string>
using namespace std;class Solution {
private:vector<string> result;     // 结果合集string path;void backtracking(const string& digits, int index) {    // index表示当前处理的数字索引if (index == digits.size()) {   // 终止条件result.push_back(path);return;}if (digits[index] > '9' || digits[index] < '0') {   // 异常处理result.clear();result.push_back("input_error");return;}else {int digit = digits[index] - '0';string letter = letterMap[digit];for (int i = 0; i < letter.size(); i++) { // 剪枝优化          path += letter[i];  // 处理节点backtracking(digits, index + 1);  // 递归path.pop_back();    // 回溯，撤销处理的节点}}}
public:const string letterMap[10] = {"", // 0"", // 1"abc", // 2"def", // 3"ghi", // 4"jkl", // 5"mno", // 6"pqrs", // 7"tuv", // 8"wxyz" // 9};vector<string> letterCombinations(string digits) {if(digits.size()) backtracking(digits, 0);           return result;}
};int main() {string digits = "*";Solution s1;vector<string> result = s1.letterCombinations(digits);for (vector<string>::iterator jt = result.begin(); jt != result.end(); jt++) {cout << *jt << " ";}cout << endl;system("pause");return 0;
}

end