Letter Combination 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.

Example: Given "23"

Return ["ad", "ae", "af", "bd", "be", "bf", "cd", "ce", "cf"]

分析：

有两种办法可以解这个题目，第一种显式定义了两个循环，第二种隐式的定义了一个循环。

解法1：

隐式方法在leetcode上

解法2：

class Solution {
public:
    /**
     * @param digits A digital string
     * @return all posible letter combinations
     */
    void dfs(string digits, string instance, vector<string>& res, int start, unordered_map<char, vector<char> > hash) {

        if (instance.size() == digits.size() ) {
            res.push_back(instance);
            return;
        }

        for (int i = start; i < digits.size(); i++) {
            for (int j = 0; j < hash[digits[i] ].size(); j++) {
                instance.push_back(hash[digits[i] ][j]);
                dfs(digits, instance, res, i + 1, hash);
                instance.pop_back();
            }
        }

    } 

    vector<string> letterCombinations(string& digits) {
        // Write your code here
        if (digits.size() == 0) {
            return vector<string>();
        }
        vector<string> res;
        string instance;

        unordered_map<char, vector<char> > hash; 
        hash['2'] = {'a', 'b', 'c'};
        hash['3'] = {'d', 'e', 'f'};
        hash['4'] = {'g', 'h', 'i'};
        hash['5'] = {'j', 'k', 'l'};
        hash['6'] = {'m', 'n', 'o'};
        hash['7'] = {'p', 'q', 'r', 's'};
        hash['8'] = {'t', 'u', 'v'};
        hash['9'] = {'w', 'x', 'y', 'z'};

        dfs(digits, instance, res, 0, hash);
        return res;
    }
};