Leetcode 17. Letter Combinations of a Phone Number

https://leetcode.com/problems/letter-combinations-of-a-phone-number/

If it just require the number, we can get it by multiplying. For specific result, DFS is a proper way to solve such problems. Of course we also can do it in other ways, while DFS is easier to understand.

Solution:

# T:O(n*4^n) S:O(n)
class Solution:
    # @param {string} digits
    # @return {string[]}
    def dfs(self, digits, string, syb):
        if digits == '':
            Solution.ret.append(string)
            return
        for ch in syb[int(digits[0])]:
            self.dfs(digits[1:], string + ch, syb)
        return
    def letterCombinations(self, digits):
        if not digits: return []
        Solution.ret, syb = [], [' ', '1', 'abc', 'def', 'ghi', 'jkl', 'mno', 'pqrs', 'tuv', 'wxyz']
        self.dfs(digits, '', syb)
        return Solution.ret

Run Time: 48 ms