17. Letter Combinations|Time:Time:O(n*4^n) | Space: O(4^n)

// Problem: https://leetcode.com/problems/letter-combinations-of-a-phone-number/
// Solution: https://www.youtube.com/watch?v=a-sMgZ7HGW0

class Solution {
    private static final String[] mapping = {
        "0",
        "1",
        "abc",
        "def",
        "ghi",
        "jkl",
        "mno",
        "pqrs",
        "tuv",
        "wxyz"
    };

    public List<String> letterCombinations(String digits) {
        List<String> mnemonics = new ArrayList<>();
        if(digits == null || digits.length() == 0) {
            return mnemonics;
        }
        char[] partialMnemonic = new char[digits.length()];

        partialMnemonicHelper(digits, 0, partialMnemonic, mnemonics);
        return mnemonics;
    }

    private void partialMnemonicHelper(String phoneNumber, int digit, char[] partialMnemonic, List<String> mnemonics) {
        if(digit == phoneNumber.length()) {
            mnemonics.add(new String(partialMnemonic));
        } else {
            for(int i = 0; i < mapping[phoneNumber.charAt(digit) - '0'].length(); i++) {
                char c = mapping[phoneNumber.charAt(digit) - '0'].charAt(i);
                partialMnemonic[digit] = c;
                partialMnemonicHelper(phoneNumber, digit + 1, partialMnemonic, mnemonics);
            }
        }
    }
}