Solution by digitalnomd

• 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:
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])\$\$.

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