8-line Backtracking-Function C++ Solution

• Most concise backtracking function, no?

``````class Solution {
public:
vector<string> letterCombinations(string digits)
{
vector<string> res;
if(digits.size()==0) return res;
string local;
vector<vector<char>> table(2,vector<char>());
table.push_back(vector<char>{'a','b','c'}); // index 2
table.push_back(vector<char>{'d','e','f'}); // 3
table.push_back(vector<char>{'g','h','i'});
table.push_back(vector<char>{'j','k','l'}); // 5
table.push_back(vector<char>{'m','n','o'});
table.push_back(vector<char>{'p','q','r','s'}); // 7
table.push_back(vector<char>{'t','u','v'});
table.push_back(vector<char>{'w','x','y','z'}); // 9

backtracking(table,res,local,0,digits);
return res;
}

void backtracking(const vector<vector<char>>& table, vector<string>& res, string& local, int index, const string& digits) {
if(index==digits.size())
res.push_back(local);
else
for(int i=0;i<table[digits[index]-'0'].size();i++) {
local.push_back(table[digits[index]-'0'][i]);
backtracking(table, res, local, index+1, digits);
local.pop_back();
}
}
};``````

• u could get the index from partial result, so four arguments 4 the backtracking function will be enough. just some personal opinion. your solution is quite nice.the difference is slight.

``````class Solution {
public:
vector<string> letterCombinations(string digits) {
vector<string> ret;
if(0>=digits.size()) return ret;

const string map[]={"0","1","abc","def","ghi","jkl","mno","pqrs","tuv","wxyz"};
backTrackingFun(map,digits,"",ret);

return ret;
}

void backTrackingFun(const string m[], const string &digits, string r, vector<string> &ret){
int c=r.size();
if(digits.size()==c){
ret.push_back(r);
return;
}

auto str = m[digits.at(c)-48];
for(auto it=str.cbegin();it!=str.cend();++it){
r.push_back(*it);
backTrackingFun(m,digits,r,ret);
r.pop_back();
}
}
};``````

• actually, by introducing a few data member, one param does suffice.

• A more concise recursive solution with only one function:

``````    string num2alpha[8] = {"abc", "def", "ghi", "jkl", "mno", "pqrs", "tuv", "wxyz"};
vector<string> letterCombinations(string digits) {
vector<string> result;
if(digits.empty()) return result;
char curDigit = digits[0];
string curStr = num2alpha[curDigit-'2'];
vector<string> subResult = letterCombinations(digits.substr(1));
if(subResult.empty()) subResult.emplace_back("");
for(int i = 0; i < curStr.length(); ++i)
{
for(int j = 0; j < subResult.size(); ++j)
{
string tmp = "";
tmp += curStr[i];
tmp = tmp + subResult[j];
result.emplace_back(tmp);
}
}
return result;
}``````

• Hi, why do you need to pop_back()?

• that's how back tracking works.

• That's because he passed in a reference of the current building string, another way to do this without the pop_back() is to pass that string by value and you don't need to pop_back().

• @pei-heng This is the method about backtracking. If without this pop_back, it's DFS. With pop_back, we can go to the previous node and continue search in another way.

• what is the time complexity of the this backtracking algorithm? is it O(4^n), n is the length of the input string.

• ``````
vector<string> letterCombinations(string digits) {
vector<string> res;
if(digits.size() == 0) return res;
string local;
vector<vector<char>> table{{'0'}, {'1'}, {'a','b','c'}, {'d','e','f'}, {'g','h','i'}, {'j','k','l'}, {'m','n','o'}, {'p','q','r','s'}, {'t','u','v'}, {'w','x','y','z'}};

backtracking(table, res, local, 0, digits);
return res;
}

void backtracking(vector<vector<char>>& table, vector<string>& res, string& local, int index, string& digits){
int digit = digits[index] - '0';

if(index == digits.size())
res.push_back(local);
else
for(int i = 0; i < table[digit].size(); i++){
local.push_back(table[digit][i]);
backtracking(table, res, local, index+1, digits);
local.pop_back();
}
}``````

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.