17. Letter Combinations of a Phone Number

# Medium

Combination of subsets and permutation methods, because start from next index instead of 0 during combination.

Solution:

1. Build a dictionary for mapping digit to characters.

2. Assume s=['abc', 'def', 'ghi'], there are 2 nested layers. Each layer needs to move to next in stead of starting from first char as permutation method. Only outside layer should remember its index.

3. Stop condition: len(level) == len(s)

class Solution:
    def letterCombinations(self, digits: str) -> List[str]:
        res = []
        # edge case
        if len(digits) == 0:
            return res
        
        dic = {'2': 'abc', '3': 'def', '4': 'ghi', '5': 'jkl', '6': 'mno', '7': 'pqrs', '8': 'tuv', '9': 'wxyz'}
        self.helper(digits, dic, 0, '', res)
        return res
        
    def helper(self, digits, dic, index, level, res):
        # add condition
        if len(level) == len(digits):
            res.append(level)
            
        for i in range(index, len(digits)):
            digit = digits[i]
            for j in dic[digit]:
                newLevel = level + j
                self.helper(digits, dic, i+1, newLevel, res)