Leetcode 17: Letter Combinations of a Phone Number

Given a digit string, return all possible letter combinations that the number could represent.
A mapping of digit to letters (just like on the telephone buttons) is given below.

Input:Digit string "23"
Output: ["ad", "ae", "af", "bd", "be", "bf", "cd", "ce", "cf"].

这个题目是典型的DFS题，是属于combination的题目。

对于DFS的题目，首先想象出DFS树，这颗DFS树有几层，每一层有几个叉，DFS的层数对应了DFS这种recursion递归

的次数，而每一层有几个叉对应了DFS在每一层中要有多少次遍历，for循环要iterate的次数。

这个题目显然DFS树有digits.size()层，每一层有phone对应的digit的字母数。 

对于手机上的字母和数字的对应关系，可以直接用string数组来表示，数组的Index就代表map中的key。

还有一点要注意的地方是digit中的元素是char,但是phone数组的index是int, 要获取phone里面的字母要

先把char 转化成int。  

class Solution {
private:
    void DFS(string digits, int level, string solu, vector<string> &rst, string phone[]) {
        //base case
        if (level == digits.size()) {
            rst.push_back(solu);
            return;
        }
        for (int i = 0; i < phone[digits[level]-'0'-1].size(); i++) {
            solu += phone[digits[level]-'0'-1][i];
            DFS(digits, level+1, solu, rst, phone);
            solu.resize(solu.size()-1);
        }
    }
public:
    //DFS solution
    vector<string> letterCombinations(string digits) {
        vector<string> rst;
        string phone[] = {"", "abc", "def","ghi","jkl","mno","pqrs","tuv","wxyz"};
        //sanity check
        if (digits.size() == 0) return rst;
        string solu = "";
        DFS(digits, 0, solu, rst, phone);
        return rst;
    }
};

time complexity: O(n^k)

space complexity: O(n)