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 digits 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: []
class Solution {
public:
unordered_map<char, string> mp {
{'2', "abc"},
{'3', "def"},
{'4', "ghi"},
{'5', "jkl"},
{'6', "mno"},
{'7', "pqrs"},
{'8', "tuv"},
{'9', "wxyz"}
};
vector<string> ans;
string st;
void solve(int id, string &digits) {
if(id == digits.size()) {
ans.push_back(st);
return;
}
for(char c: mp[digits[id]]) {
st.push_back(c);
solve(id+1, digits);
st.pop_back();
}
}
vector<string> letterCombinations(string digits) {
if(digits.size() == 0) return ans;
solve(0, digits);
return ans;
}
};
