leetcode-17 Letter Combinations of a Phone Number

    cur_str = cur_str[:-1]  # backtrack

# Given a string containing digits from 2-9 inclusive, return all possible
# letter 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'].

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

        dic = {
            '2': 'abc',
            '3': 'def',
            '4': 'ghi',
            '5': 'jkl',
            '6': 'mno',
            '7': 'pqrs',
            '8': 'tuv',
            '9': 'wxyz'      
        }

        ret = []
        n = len(digits)

        def dfs(i, cur_str):
            if i == n:
                ret.append(cur_str)
                return

            for ch in dic[digits[i]]:
                cur_str += ch
                dfs(i + 1, cur_str)
                cur_str = cur_str[:-1]  # backtrack

        dfs(0, "")

        return ret