#coding:utf-8
# Given a digit string, return all possible letter combinations that the number could represent.
#
# A mapping of digit to letters (just like on the telephone buttons) is given below.

# Input:Digit string "23"
# Output: ["ad", "ae", "af", "bd", "be", "bf", "cd", "ce", "cf"].

def solution(digits):
    numWordMap = {
        '2': ['a', 'b', 'c'],
        '3': ['d', 'e', 'f'],
        '4': ['g', 'h', 'i'],
        '5': ['j', 'k', 'l'],
        '6': ['m', 'n', 'o'],
        '7': ['p', 'q', 'r', 's'],
        '8': ['t', 'u', 'v'],
        '9': ['w', 'x', 'y', 'z']
    }

    result = []
    for i, v in enumerate(digits):
        if v == '1':
            continue
        if i == 0:
            result = numWordMap[v]
            continue
        newArr = []
        for i in numWordMap[v]:
            for j in result:
                newArr.append(j + i)
        result = newArr
    return result

print solution("23")
