title
Given a string containing digits from 2-9 inclusive, 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. Note that 1 does not map to any letters.
Example:
Input: “23”
Output: [“ad”, “ae”, “af”, “bd”, “be”, “bf”, “cd”, “ce”, “cf”].
solution
bfs
class Solution {
public:
void dof(vector<string> &str, vector<string> &res, string s, string digits,int index) {
if (index == digits.length()) {
res.push_back(s);
cout << s << endl;
return;
}
string t = str[digits[index] - '0'];
for (char c : t) {
dof(str, res, s + c, digits, index + 1);
}
}
vector<string> letterCombinations(string digits) {
vector<string> str= { "", "", "abc", "def", "ghi", "jkl", "mno", "pqrs", "tuv", "wxyz" };
vector<string> res;
if (digits.length() == 0) return res;
dof(str, res, "", digits, 0);
return res;
}
};