'''
给定一个仅包含数字 2-9 的字符串，返回所有它能表示的字母组合。

给出数字到字母的映射如下（与电话按键相同）。注意 1 不对应任何字母。
'''
#dp[i]表示前i个字母的所有组合,dp[i-1]只与dp[i]有关
def letterCombinary(digits):
    if not digits:
        return []
    d={'2': 'abc', '3': 'def', '4': 'ghi', '5': 'jkl',
        '6': 'mno', '7': 'pqrs', '8': 'tuv', '9': 'wxyz'}

    n=len(digits)
    res=['']
    for i in range(n):
        res=[x+y for x in res for y in d[digits[i]]]
    return res