'use strict';

// Solution to Question 17 "Letter Combinations of a Phone number using DFS backtracking"

const mappings = {
    1: "",
    2: "abc",
    3: "def",
    4: "ghi",
    5: "jkl",
    6: "mno",
    7: "pqrs",
    8: "tuv",
    9: "wxyz"
};

/**
 * @param {string} digits
 * @return {string[]}
 */
var letterCombinations = function(digits) {
    if (digits == null || digits === "") {
        return [];
    }
    // initialize the result array
    let res = [];
    // keep track of the current index of digit we are looking at
    let currIdx = 0;
    // keep track of the current substring we are exploring
    let currStr = "";
    // start recursion
    backtracking(res, digits, currIdx, currStr);
    return res;
};

var backtracking = function (res, digits, currIdx, currStr) {
    if (currIdx === digits.length) {
        // one of the solution now is complete, push it to the array
        return res.push(currStr);
    }
    // get the current character
    const c = digits[currIdx];
    // get its mapping
    const mapping = mappings[c];
    // iterate through every character in the mapping
    for (const s of mapping) {
        currStr += s;
        // recursion
        backtracking(res, digits, currIdx + 1, currStr);
        // revert currStr back
        currStr = currStr.slice(0, -1);
    }
};