class Solution {

    public List<String> letterCombinations(String digits) {
        if (digits == null || digits.length() == 0) return new ArrayList<>();

        Map<Character, String> map = new HashMap<>();
        map.put('2', "abc");
        map.put('3', "def");
        map.put('4', "ghi");
        map.put('5', "jkl");
        map.put('6', "mno");
        map.put('7', "pqrs");
        map.put('8', "tuv");
        map.put('9', "wxyz");

        List<String> result = new ArrayList<>();
        _generate(result, map, digits, 0, "");
        return result;

    }


  public void _generate(List<String> result, Map<Character, String> map, String digits, int index, String s) {
    // terminator
    if (index == digits .length()) {
      result.add(s);
      return;
    }
    // process
    String letters = map.get(digits.charAt(index));
    for (int i = 0; i < letters.length(); i++) {
        // drill down
        _generate(result, map, digits, index + 1, s + letters.charAt(i));    
    }
    // reverse states
  }
}

class Solution:
    def letterCombinations(self, digits: str) -> List[str]:
      if not digits:
        return []

      self.result = []
      self.d = {
        '2': 'abc',
        '3': 'def',
        '4': 'ghi',
        '5': 'jkl',
        '6': 'mno',
        '7': 'pqrs',
        '8': 'tuv',
        '9': 'wxyz'
      }

      self.dfs(digits, [], 0)
      return self.result

    def dfs(self, digits, temp, index):
      if len(temp) == len(digits):
        self.result.append("".join(x for x in temp))
        return

      for c in self.d[digits[index]]:
        temp.append(c)
        self.dfs(digits, temp, index+1)
        temp.pop()