https://leetcode-cn.com/problems/letter-combinations-of-a-phone-number/

我的方法一：递归

求长度是n的数字，我们可以先求出n-1长度数字的字母组合，然后在所有的组合前面再加上第n为数字的字母列表

递归方程：

f(n) =foreach lookup(digits[n]) : foreach f(n-1)

初始条件和边界条件

当digits长度为0时，直接返回空vector

代码

class Solution {
public:
    //递归
    vector<string> letterCombinations(string digits) {
        static string lookup[] = {
            "abc",
            "def",
            "ghi",
            "jkl",
            "mno",
            "pqrs",
            "tuv",
            "wxyz"
        };

        vector<string> ret;
        if(digits.size() == 0){
            return ret;
        }else if(digits.size() == 1){
            string lu = lookup[digits.c_str()[0] - '2'];
            for(int i=0; i<lu.size(); i++){
                ret.push_back(string(lu.c_str()+i, 1));
            }
            return ret;
        }
        
        string sub_digits(digits.c_str()+1);
        vector<string> sub_ret = letterCombinations(sub_digits);
        string lu = lookup[digits.c_str()[0] - '2'];
        for(int i=0; i<lu.size(); i++){
            for(auto & sub : sub_ret){
                ret.push_back(string(lu.c_str()+i, 1) + sub);
            }
        }
        return ret;
    }
};

我的方法二：迭代

和递归类似

代码

class Solution {
public:
    //迭代
    vector<string> letterCombinations(string digits) {
        static string lookup[] = {
            "abc",
            "def",
            "ghi",
            "jkl",
            "mno",
            "pqrs",
            "tuv",
            "wxyz"
        };

        vector<string> ret;
        int ret_size = ret.size();
        for(int i = 0; i<digits.size(); i++){
            string lu = lookup[digits.c_str()[i] - '2'];
            ret_size = ret.size();
            if(ret_size == 0){
                for(int j = 0; j<lu.size(); j++){
                    ret.push_back(string(lu.c_str() + j, 1));
                }
            }else{
                for(int j = 0; j<lu.size(); j++){
                    for(int k = 0; k<ret_size; k++){
                        ret.push_back(ret[k] + string(lu.c_str() + j, 1));
                    }
                }
                for(int k = 0; k<ret_size; k++){
                    ret.erase(ret.begin());
                }
            }
        }        
        return ret;
    }
};