lc-17

//Given a string containing digits from 2-9 inclusive, return all possible lette
//r combinations that the number could represent. Return the answer in any order. 
//
//
// A mapping of digits to letters (just like on the telephone buttons) is given 
//below. Note that 1 does not map to any letters. 
//
// 
// Example 1: 
//
// 
//Input: digits = "23"
//Output: ["ad","ae","af","bd","be","bf","cd","ce","cf"]
// 
//
// Example 2: 
//
// 
//Input: digits = ""
//Output: []
// 
//
// Example 3: 
//
// 
//Input: digits = "2"
//Output: ["a","b","c"]
// 
//
// 
// Constraints: 
//
// 
// 0 <= digits.length <= 4 
// digits[i] is a digit in the range ['2', '9']. 
// 
// Related Topics Hash Table String Backtracking 
// 👍 10965 👎 707


//leetcode submit region begin(Prohibit modification and deletion)
class Solution {
    public List<String> letterCombinations(String digits) {
        Map<Character, String> myMap = new HashMap<>();
        myMap.put('2', "abc");
        myMap.put('3', "def");
        myMap.put('4', "ghi");
        myMap.put('5', "jkl");
        myMap.put('6', "mno");
        myMap.put('7', "pqrs");
        myMap.put('8', "tuv");
        myMap.put('9', "wxyz");

        List<String> result = null;

        if (digits == null || digits.length() == 0) {
            return new ArrayList<>();
        }

        for (int i = 0; i < digits.length(); i++) {
            result = getNext(result, myMap, digits, i);
        }

        return result;
    }

    private List<String> getNext(List<String> curList,  Map<Character, String> myMap, String digits, int index) {
        if (index >= digits.length()) {
            return curList;
        }

        char ch = digits.charAt(index);
        String charsStr = myMap.get(ch);
        List<String> result = new ArrayList<>();

        for (char repCh : charsStr.toCharArray()) {
            if (curList == null) {
                result.add("" + repCh);
            } else {
                for (String curStr : curList) {
                    result.add(curStr + repCh);
                }
            }
        }

        return result;

    }
}
//leetcode submit region end(Prohibit modification and deletion)