Letter Combinations of a Phone Number

Description

Given a digit string excluded01, 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.

Notice

Although the above answer is in lexicographical order, your answer could be in any order you want.

Example

Given"23"

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

Implementation

Link: http://lintcode.com/en/problem/letter-combinations-of-a-phone-number/

class Solution {
public:
    /**
     * @param digits A digital string
     * @return all posible letter combinations
     */
    vector<string> letterCombinations(string& digits) {
        // Write your code here
        vector<string> mapping = {" ", "", "abc", "def", "ghi", "jkl", "mno", "pqrs", "tuv", "wxyz"};
        vector<string> ret;
        string path;

        if(digits.size() == 0) return ret;

        helper(digits, ret, path, mapping, 0);
        return ret;
    }

    void helper(string & digits, vector<string> & ret, string & path, vector<string> & mapping, int step){
        if(step == digits.size()){
            ret.push_back(path);
            return;
        }

        for(int i = 0; i < mapping[digits[step] - '0'].size(); i++){
            path.push_back(mapping[digits[step] - '0'][i]);
            helper(digits, ret, path, mapping, step + 1);
            path.pop_back();
        }
    }
};