电话号码的字母组合

发布于 2020-07-17 12:23:03   阅读量 44  点赞 0  

原题地址:https://leetcode-cn.com/problems/letter-combinations-of-a-phone-number/

题目

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

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

示例:

输入:"23"
输出:["ad", "ae", "af", "bd", "be", "bf", "cd", "ce", "cf"].


说明:
 尽管上面的答案是按字典序排列的,但是你可以任意选择答案输出的顺序。



解法

 察觉到每个规模为n的问题都能被拆解为规模为n-1的子问题来进行求解,于是使用动态规划来求解问题。例如对于输入"456",可以拆解为子串"45"的组合结果与"6"对应的字符m,n,o的排列组合,而子串"45"又能拆解为"4""5"对应字符的排列组合。从子问题得出父问题只需经过两个字符串集合的排列组合即可,从而将原问题简单化。

 首先声明一个数组,保存每次递归中产生的子问题的结果(即子串的解),然后求解当前问题时,将子问题的解与当前字符进行组合即可。

优化:
 由于求解每个问题时,无需用到原问题分割而成的每个子问题的解,只需用到当前问题的子问题的解。故无需保存所有子问题,只需保存当前求问题的解,来作为下次迭代的问题的子问题。于是使用长度为2的数组交替使用,并使用双指针currentprevent,来指示当前处理的问题与当前问题的子问题即可,从而降低算法的空间开销。


代码

vector<string> letterCombinations(string digits) {
    // 使用string数组来表示数字与字母间的对应关系
    // 通过 下标+2 来访问某个数字对应的所有字符
    string data[8]={"abc","def","ghi","jkl","mno","pqrs","tuv","wxyz"};

    // 获取输入的所有数字
    vector<int> input = vector<int>();
    for(char c:digits){
        int number = c-48;
        input.push_back(number);
    }

    // 声明一个长度为2的 vector<string> 数组,来缓存前一次计算的结果
    vector<string> cache[2];

    // 定义两个指针,来指示缓存中当前操作的向量
    int current = 0;
    int prevent = 1;
    // 动态规划
    for(int i=0;i<input.size();i++){
        cache[current].clear();

        // 对于输入的第i个数字
        vector<string> vec = vector<string>();
        if(i==0){
            // 若为递归边界
            for(char c:data[input[i]-2]){
                cache[current].push_back(string("")+c);
            }
        }else{
            for(const string& s:cache[prevent]){
                for(char c:data[input[i]-2]){
                    cache[current].push_back(s+c);
                }
            }
        }
        current = current + prevent;
        prevent = current - prevent;
        current = current - prevent;
    }
    return cache[prevent];
}


Last Modified : 2020-09-27 01:30:18