Solution by digitalnomd


  • 0
    D

    Approach #1 Backtracking [Accepted]

    Intuition

    We need to find a way to build each string that will be added to our list of combinations such that we only add one character for every digit-to-character string mapping.

    The above can be accomplished by using a backtracking approach.

    Algorithm

    First build a list of mappings from digits to characters. Next get all possible combinations of those mappings by adding one character at a time and recursively popping each mapping off of the queue.

    Python

    from collections import deque
    
    class Solution(object):
        def letterCombinations(self, digits):
            """
            :type digits: str
            :rtype: List[str]
            """
            maps = {
                "2": "abc", "3": "def",
                "4": "ghi", "5": "jkl",
                "6": "mno", "7":"pqrs",
                "8": "tuv", "9": "wxyz"
            }
    
            if "0" in digits or "1" in digits: return []
    
            nMaps = deque([maps[d] for d in digits])
            combos = set()
    
            def getCombos(combo, nMaps):
                if bool(nMaps) == False:
                    if bool(combo) and combo not in combos:
                        combos.add(combo)
                    return
                m = nMaps.popleft()
                for c in m:
                    getCombos(combo + c, nMaps)
    
                nMaps.appendleft(m)
    
            getCombos("", nMaps)
            return list(combos)
    

    Complexity Analysis

    • Time complexity : O(\prod\limits_{i=1}^n A[d].length, d = digts[i])$$.

    The generation of all the character combinations dominates the time-complexity. The number of number mappings is equal to the product of all digit-to-character mappings or $$A$$.

    • Space complexity : $$O(\prod\limits_{i=1}^n digits.length * A[d].length, d = digts[i])$$.

Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.