class Solution:
    # @return a list of strings, [s1, s2]
    def letterCombinations(self, digits):
        digits = digits.replace('1', '')
        if digits == '': return ['']
        phone = {'0':' ', '2':'abc', '3':'def', '4':'ghi', '5':'jkl', '6':'mno', '7':'pqrs', '8':'tuv', '9':'wxyz'}
        res = []; new_res = []; length = len(digits)
        for i in phone[digits[0]]: 
            res.append([i])
            new_res.append([i])
        for i in xrange(1, length):
            new_res = []
            for item in res:
                for letter in phone[digits[i]]:
                    new_res.append(item + [letter])
            res = new_res
        res = []
        for item in new_res:
            res.append(''.join(item))
        return res