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"].Answer:
C++ version:
class Solution {
public:
vector<string> letterCombinations(string digits) {
string mmap[] = {"", " ", "abc", "def", "ghi", "jkl",
"mno", "pqrs", "tuv", "wxyz"};
vector<string> res;
string seq;
Generater(mmap, digits, 0, seq, res);
return res;
}
void Generater(string mmap[], string& digits, int level, string& subres, vector<string>& res){
if(level == digits.size()){
res.push_back(subres);
return;
}
int digint = digits[level] - '0';
for(int i =0; i < mmap[digint].size(); i++){
subres.push_back(mmap[digint][i]);
Generater(mmap, digits, level+1, subres,res);
subres.resize(subres.size() -1);
}
}
};
Java version:
public class Solution {
public List<String> letterCombinations(String digits) {
String[] mmap = {""," ","abc","def","ghi","jkl", "mno", "pqrs", "tuv", "wxyz"};
List<String> res = new ArrayList<String>();
String subres = new String();
generate(mmap, digits, 0, subres, res);
return res;
}
public void generate(String[] mmap, String digits, int idx, String subres, List<String> res){
if(idx == digits.length()){
res.add(subres);
return;
}
int digit = digits.charAt(idx) - '0';
for(int i=0; i<mmap[digit].length();++i){
subres += mmap[digit].charAt(i);
generate(mmap, digits, idx+1, subres, res);
subres = subres.substring(0,subres.length()-1);
}
return;
}
}
No comments:
Post a Comment