17. Letter Combinations of a Phone Number.md

17. Letter Combinations of a Phone Number

思路

思路一

举例说明吧。

1. digits = "2"时，结果显然是res = ["a","b","c"]；
2. digits = "23"时，1中res的每一个字符串后都可以接d、e、f任意一个，所以可以先将1中的res中所有元素复制两遍 变成["a","b","c","a","b","c","a","b","c"]，再在此时res的每一个元素后面合适地接上d、e、f其中一个就变成了 ["ad","bd","cd","ae","be","ce","af","bf","cf"]。

由此就可以写出代码了。
时间复杂度O(n^2)，空间复杂度O(1)

思路二

其实可以将此题看成求解一棵树的所有root(root可以看做是空)到叶子的路径。
例如当digits = "23"时，树应该是这个样子:

          root
        /   |   \
  2:   a    b    c
      /|\  /|\  /|\
  3:  def  def  def

所以就可以用DFS求解这题了。

C++

思路一

class Solution {    
public:
    vector<string> letterCombinations(string digits) {
        int len = digits.size();
        vector<string>res;
        if(len == 0) return res;
        
        const vector<string>digit2char{"","","abc","def","ghi",
                                        "jkl","mno","pqrs","tuv","wxyz"};
        res.push_back("");
        for(int i = 0; i < len; i++){
            int digit = int(digits[i] - '0');
            int curr_res_size = res.size();
            for(int k = 0; k < digit2char[digit].size() - 1; k++) // 将res中所有元素复制几遍
                for(int j = 0; j < curr_res_size; j++) 
                    res.push_back(res[j]);
            for(int k = 0; k < digit2char[digit].size(); k++)
                for(int j = 0; j < curr_res_size; j++)
                    res[k * curr_res_size + j] += digit2char[digit][k];
        }
        return res;
        
    }
};

思路二

class Solution {
private:
    const vector<string>digit2char{"", "", "abc", "def", "ghi", "jkl", "mno", "pqrs", "tuv", "wxyz"};
    void DFS(const string &digits, string out, vector<string> &res){
        int start = out.size();
        if(start == digits.size()){
            res.push_back(out);
            return;
        }
        for(char c: digit2char[digits[start]-'0'])
            DFS(digits, out+c, res);
    }
public:
    vector<string> letterCombinations(string digits) {
        vector<string>res;
        if(digits.size() == 0) return res;
        string out;
        DFS(digits, out, res);
        return res;
    }
};