题目描述

原题链接：17. 电话号码的字母组合

解题思路

1. 构建电话数字和字母映射关系
2. 回溯操作，选择一个数字的中对应的一个字母。

哈希表映射

用Hash表构建字符型数字和字母的映射关系。

class Solution {
public:
    // 记录结果集
    vector<string> res;     
    // 构建电话数字和字母的映射关系
    void buildNumString(map<char, string> &table) {
        char startIndex = 'a';
        for(char i = '2'; i <= '9'; i++) {
            string s = "";
            char ch = startIndex;
            while(ch <= startIndex + 2 && ch <= 'z') {
                s += ch++;
            }         
            if(i == '7') {
                ch = 't';
                s += 's';
            }
            startIndex = ch;
            table[i] = s;
        }
        table['9'] += "z"; 
    }
    // digits：输入数字，s：已记录对应字母，startIndex：起始下标，table：映射表
    void backtracking(string digits, string s, int startIndex, map<char, string> table) {        
        if(s.size() == digits.size()) {
            res.push_back(s);
        }        
        // 外层遍历输入的数字，内层遍历每个数字对应的字母，每次更新起始下标
        for(int i = startIndex; i < digits.size(); i++) {
            for(int j = 0; j < table[digits[i]].size(); j++) {
                backtracking(digits, s + table[digits[i]][j], i + 1, table);
            }            
        }
    }
    vector<string> letterCombinations(string digits) {
        if(digits.size() == 0)          return {};
        map<char, string> table;
        buildNumString(table);
        backtracking(digits, "", 0, table);

        return res;
    }
};

代码优化：字符串数组映射

将Hash表改用string数组，降低空间复杂度、提高了存储效率。

class Solution {
public:
    // 记录结果集
    vector<string> res;     
    // 构建电话数字和字母的映射关系
    void buildNumString(string table[]) {
        table[0] = "";
        table[1] = "";
        char startIndex = 'a';
        for(int i = 2; i <= 9; i++) {
            string s = "";
            char ch = startIndex;
            while(ch <= startIndex + 2 && ch <= 'z') {
                s += ch++;
            }
            if(i == 7) {
                ch = 't';
                s += 's';
            }
            startIndex = ch;
            table[i] = s;
        }
        table[9] += "z";             
    }
    // digits：输入数字，s：已记录对应字母，startIndex：遍历的数字下标，table：映射表
    void backtracking(string digits, string s, int startIndex, string table[]) {        
        if(s.size() == digits.size()) {
            res.push_back(s);
            return ;
        }        
        // 获取遍历的数字和对应的字母串
        int digit = digits[startIndex] - '0';
        string letters = table[digit];
        // 遍历该数字对应的字母串
        for(int i = 0; i < letters.size(); i++) {
            backtracking(digits, s + letters[i], startIndex + 1, table);
        }
    }
    vector<string> letterCombinations(string digits) {
        if(digits.size() == 0)          return {};
        string table[10];
        buildNumString(table);
        backtracking(digits, "", 0, table);

        return res;
    }

};

参考文章：17.电话号码的字母组合