Phone Number Combinations - Amazon Top Interview Questions

                        Solution in C++ :

vector<string> keypad = {"", "", "abc", "def", "ghi", "jkl", "mno", "pqrs", "tuv", "wxyz"};

vector<string> solve(string digits) {
    if (digits.empty()) return {""};
    vector<string> answers;
    for (auto first : keypad[digits[0] - '0']) {
        for (auto rest : solve(digits.substr(1))) {
            answers.push_back(first + rest);
        }
    }
    return answers;
}
                    

                        Solution in Java :

import java.util.*;

class Solution {
    public String[] solve(String digits) {
        Map<Character, char[]> digitToChars = new HashMap<>();
        digitToChars.put('2', new char[] {'a', 'b', 'c'});
        digitToChars.put('3', new char[] {'d', 'e', 'f'});
        digitToChars.put('4', new char[] {'g', 'h', 'i'});
        digitToChars.put('5', new char[] {'j', 'k', 'l'});
        digitToChars.put('6', new char[] {'m', 'n', 'o'});
        digitToChars.put('7', new char[] {'p', 'q', 'r', 's'});
        digitToChars.put('8', new char[] {'t', 'u', 'v'});
        digitToChars.put('9', new char[] {'w', 'x', 'y', 'z'});

        List<String> collector = new ArrayList<>();
        backtrack(digits, 0, digitToChars, new StringBuilder(), collector);

        return collector.toArray(new String[collector.size()]);
    }

    private void backtrack(String digits, int idx, Map<Character, char[]> digitToChars,
        StringBuilder sb, List<String> collector) {
        if (digits.length() == idx) {
            collector.add(sb.toString());
        } else {
            for (char c : digitToChars.get(digits.charAt(idx))) {
                sb.append(c);
                backtrack(digits, idx + 1, digitToChars, sb, collector);
                sb.deleteCharAt(sb.length() - 1);
            }
        }
    }
}
                    

                        Solution in Python : 
                            
class Solution:
    def solve(self, digits):
        phone = {}
        phone["2"] = list("abc")
        phone["3"] = list("def")
        phone["4"] = list("ghi")
        phone["5"] = list("jkl")
        phone["6"] = list("mno")
        phone["7"] = list("pqrs")
        phone["8"] = list("tuv")
        phone["9"] = list("wxyz")

        result = []
        curr = []

        def build(d, curr):
            nonlocal phone, result

            if len(d) == 0:
                result.append("".join(curr))
                return

            for i in phone[d[0]]:
                curr.append(i)
                build(d[1:], curr)
                curr.pop()

        build(list(digits), [])

        return result