LeetCode: Letter Combinations of a Phone Number

Title:

https://leetcode.com/problems/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搜索

class Solution {
public:
    map<int,string> digitsMap;
    Solution(){
        digitsMap[0]="";
        digitsMap[1]="";
        digitsMap[2] = "abc";
        digitsMap[3] = "def";
        digitsMap[4] = "ghi";
        digitsMap[5] = "jkl";
        digitsMap[6] = "mno";
        digitsMap[7] = "pqrs";
        digitsMap[8] = "tuv";
        digitsMap[9] = "wxyz";
    }
    vector<string> letterCombinations(string digits) {
        vector<string> result;
        if (digits=="")
            return result;
        string ret = "";
        dfs(0,digits,ret,result);
        return result;
    }
    void dfs(int index, string s, string ret,vector<string>& result){
        if (index == s.size()){
            result.push_back(ret);
            return ;
        }
        string tmp = digitsMap[s[index]-'0'];
        for (int i = 0 ; i < tmp.size(); i++){
            ret.push_back(tmp[i]);
            dfs(index+1,s,ret,result);
            ret.pop_back();
        }
        if (index == 0)
            return ;
    }
};