[LeetCode] Letter Combinations of a Phone Number

 

Given a string containing digits from 2-9 inclusive, return all possible letter combinations that the number could represent. Return the answer in any order.

A mapping of digit to letters (just like on the telephone buttons) is given below. Note that 1 does not map to any letters.

 

Example 1:

Input: digits = "23" Output: ["ad","ae","af","bd","be","bf","cd","ce","cf"]

Example 2:

Input: digits = "" Output: []

Example 3:

Input: digits = "2" Output: ["a","b","c"]

 

Constraints:

• 0 <= digits.length <= 4
• digits[i] is a digit in the range ['2', '9'].

class Solution {
public:
    map<char, vector<char>> al;
    string addDigits(vector<string>& ans, string s, string digits, int num)
    {
        string str = "";
        if (num < digits.length())
        {
            for (int i = 0; i < al[digits[num]].size(); i++)
            {
                str = s + al[digits[num]][i];
                addDigits(ans, str, digits, num + 1);
                if (num == digits.length() - 1)
                {
                    ans.push_back(str);
                }
            }
        }
        else if (num == 1)
        {
            ans.push_back(s);
        }
        return str;
    }
    vector<string> letterCombinations(string digits) {
        vector<string> ans;
        int start = 97;
        for (int i = 0; i < 8; i++)
        {
            if (i + 2 == 7)
            {
                al['7'].push_back('p');
                start++;
            }
            if (i + 2 == 9)
            {
                al['9'].push_back('w');
                start++;
            }
            for (int j = 0; j < 3; j++)
            {
                al[to_string(i + 2)[0]].push_back((char)(start+(3*i)+j));
            }
        }
        for (int i = 0; i < al[digits[0]].size(); i++)
        {
            string s(1, al[digits[0]][i]);
            addDigits(ans, s, digits, 1);
        }
        return ans;
    }
};