17. Letter Combinations of a Phone Number

When I first looked at this problem, I immediately recognized it as a DFS / Backtracking problem. As I read more about solving backtracking problems, one key idea stood out:

“Think from the perspective of a node rather than the whole tree.”

So, first I converted the input to a proper vector to process.

private:
    vector<char> mapping(char digit){
        int INTDigit = digit - '0';
        vector<char> result;
        switch(INTDigit){
            case 2: return {'a', 'b', 'c'};
            case 3: return {'d', 'e', 'f'};
            case 4: return {'g', 'h', 'i'};
            case 5: return {'j', 'k', 'l'};
            case 6: return {'m', 'n', 'o'};
            case 7: return {'p', 'q', 'r', 's'};
            case 8: return {'t', 'u', 'v'};
            case 9: return {'w', 'x', 'y', 'z'};
            default: return {};
        }
    }
public:
    vector<string> letterCombinations(string digits) {
        vector<vector<char>> vec;
        for(int i=0; i<digits.size(); i++){
            vec.push_back(mapping(digits[i]));
        }
    }

Now, looking at the parameters which I would be needing:

vector globalResult to store all the combinations
string localResult which I will keep modifying and use to store the permutations
int vectorpos = 0; // To process each node / vector

int n = digits.size();
int vectorpos = 0;
vector<string> globalResult;

Now, I would need to traverse through the first vector only and with each character I would do dfs for the next vector, so, I would pass in vectorpos + 1 to the dfs.

for(int i=0; i<vec[vectorpos].size(); i++){
    string localResult = string(1, vec[vectorpos][i]);
    dfs(vec, localResult, globalResult, vectorpos + 1, n);
}

Now, comes the main part of writing the dfs

Base case:

void dfs(vector<vector<char>>& vec, string localResult, vector<string>& globalResult, int vectorpos, int n){
    if(vectorpos >= n){
        globalResult.push_back(localResult);
        return ;
    }
}

Now since the vectors are not exhausted, I can process this (vectorpos) vector. Therefore, I will proceed with processing and then perform DFS on this vector from the start.

for(int i = 0; i < vec[vectorpos].size(); i++){
    localResult.push_back(vec[vectorpos][i]);
    dfs(vec, localResult, globalResult, vectorpos + 1, n);
}

It doesn’t end here! Since a reference to localResult is passed, when we come back to this vector we would be appending the next character to this vector, along with the last inserted character.

Example:

["a", "b", "c"]

For i = 0 We would be inserting: localResult = “a” + dfs(….) For i = 1 It would become “a” + “b” + …

Therefore we need to remove “a” as well, so we do a pop_back();

Complete function:

for(int i=0; i < vec[vectorpos].size(); i++){
        localResult.push_back(vec[vectorpos][i]);
        dfs(vec, localResult, globalResult, vectorpos + 1, n);
        localResult.pop_back();
    }

So, complete code becomes:

class Solution {
private:
    vector<char> mapping(char digit){
        int INTDigit = digit - '0';
        vector<char> result;
        switch(INTDigit){
            case 2: return {'a', 'b', 'c'};
            case 3: return {'d', 'e', 'f'};
            case 4: return {'g', 'h', 'i'};
            case 5: return {'j', 'k', 'l'};
            case 6: return {'m', 'n', 'o'};
            case 7: return {'p', 'q', 'r', 's'};
            case 8: return {'t', 'u', 'v'};
            case 9: return {'w', 'x', 'y', 'z'};
            default: return {};
        }
    }

void dfs(vector<vector<char>>& vec, string localResult, vector<string>& globalResult, int vectorpos, int n){
    if(vectorpos >= n){
        globalResult.push_back(localResult);
        return ;
    }
    for(int i=0; i < vec[vectorpos].size(); i++){
        localResult.push_back(vec[vectorpos][i]);
        dfs(vec, localResult, globalResult, vectorpos + 1, n);
        localResult.pop_back();
    }
}

public:
    vector<string> letterCombinations(string digits) {
        if(digits.size() == 0) return {};
        vector<vector<char>> vec;
        for(int i=0; i<digits.size(); i++){
            vec.push_back(mapping(digits[i]));
        }
        int n = digits.size();
        int vectorpos = 0;
        vector<string> globalResult;
        for(int i=0; i<vec[vectorpos].size(); i++){
            string localResult = string(1, vec[vectorpos][i]);
            dfs(vec, localResult, globalResult, vectorpos + 1, n);
        }
        return globalResult;
    }
};

Example:#

Example: