#! /usr/bin/env python

'''
Letter Combinations of a Phone Number 

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"].
Note:
Although the above answer is in lexicographical order, your answer could be in any order you want.

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

class Solution:
    # @return a list of strings, [s1, s2]
    def letterCombinations(self, digits):
        self.mapping = {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')}
        self.output = []

        self.generateCombis(digits, "")
        return self.output

    def generateCombis(self,digits,pre_fix):
        if len(digits) == 0:
            self.output.append(pre_fix)
            return
        else:
            for i in self.mapping[int(digits[0])]:
                self.generateCombis(''.join(digits[1:]),pre_fix+i)

if __name__ == "__main__":
    s = Solution()
    print s.letterCombinations('23') 
            
        
            
            

    
        
