#https://leetcode.com/problems/letter-combinations-of-a-phone-number
class Solution:
    combination = []
    def backtrack(self,arr,pos,level,current,t,digits):

        if level >= t:
            return


        if pos >= len(arr[digits[level]-2]):
            return




        current.append(arr[digits[level]-2][pos])
        self.backtrack(arr,0,level+1,current,t,digits)

        if level == t-1:
            self.combination.append(current.copy())

        current.pop(-1)
        self.backtrack(arr,pos+1,level,current,t,digits)
        current =[]
        return


    def letterCombinations(self, digits: str) -> List[str]:

        # 2,3 -> ad,ae,af,bd,be,bf,cd,ce,cf
        self.combination = []

        let = {
            0 : "abc",
            1 : "def",
            2 : "ghi",
            3 : "jkl",
            4 : "mno",
            5 : "pqrs",
            6 : "tuv",
            7 : "wxyz"
        }

        digits = [int(a) for a in digits]


        current = []
        pos = 0
        level = 0
        self.backtrack(arr=let,pos=pos,level=level,current=current,t=len(digits),digits=digits)


        # print([ "".join(x) for x in self.combination])

        #print(self.combination)


        return [ "".join(x) for x in self.combination]