Given a string containing digits from 2-9 inclusive, 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. Note that 1 does not map to any letters.



Example:


Input: "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.

Source: leetcode | Difficulty: MEDIUM_HARD
Tags: String algorithms

Data structures

Complete search

Starter code: class Solution:
    def letterCombinations(self, digits: str) -> List[str]:
        

Solutions:
class Solution:

	def letterCombinations(self, digits):

		def dfs(digits, current, result):
			if not digits:
				result.append(current)
				return
			for c in dic[digits[0]]:
				dfs(digits[1:], current + c, result)
		if not digits:
			return []
		dic = {'2': 'abc', '3': 'def', '4': 'ghi', '5': 'jkl', '6': 'mno', '7': 'pqrs', '8': 'tuv', '9': 'wxyz'}
		result = []
		dfs(digits, '', result)
		return result


class Solution:

	def letterCombinations(self, digits):
		if not digits:
			return []
		MAPPING = ('0', '1', 'abc', 'def', 'ghi', 'jkl', 'mno', 'pqrs', 'tuv', 'wxyz')

		def directed_combinations(i, partial):
			if i == len(digits):
				result.append(''.join(partial))
				return
			for c in MAPPING[int(digits[i])]:
				directed_combinations(i + 1, partial + [c])
		result = []
		directed_combinations(0, [])
		return result


class Solution:

	def letterCombinations(self, digits):
		dic = {'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']}
		if '0' in digits:
			digits = digits.replace('0', '')
		if '1' in digits:
			digits = digits.replace('1', '')
		count = 0
		for a in '23456789':
			if a not in digits:
				count += 1
		if count == 8:
			return []
		res = []
		temp = ['']
		i = 0
		while i < len(digits):
			for a in temp:
				for b in dic[digits[i]]:
					res.append(a + b)
			temp = res
			res = []
			i += 1
		return temp


class Solution:

	def letterCombinations(self, digits):
		if '' == digits:
			return []
		kvmaps = {'2': 'abc', '3': 'def', '4': 'ghi', '5': 'jkl', '6': 'mno', '7': 'pqrs', '8': 'tuv', '9': 'wxyz'}
		rst = ['']
		for digit in digits:
			temp = [s + c for s in rst for c in kvmaps[digit]]
			rst = temp
		return rst


class Solution:

	def letterCombinations(self, digits):
		if digits == None or len(digits) == 0:
			return []
		res = []
		cur = ''
		dmap = {}
		dmap['0'] = [' ']
		dmap['1'] = []
		dmap['2'] = ['a', 'b', 'c']
		dmap['3'] = ['d', 'e', 'f']
		dmap['4'] = ['g', 'h', 'i']
		dmap['5'] = ['j', 'k', 'l']
		dmap['6'] = ['m', 'n', 'o']
		dmap['7'] = ['p', 'q', 'r', 's']
		dmap['8'] = ['t', 'u', 'v']
		dmap['9'] = ['w', 'x', 'y', 'z']
		self.dfs(digits, dmap, 0, cur, res)
		return res

	def dfs(self, digits, dmap, idx, cur, res):
		if idx == len(digits):
			res.append(cur)
			return
		else:
			c = digits[idx]
			for i in dmap[c]:
				self.dfs(digits, dmap, idx + 1, cur + i, res)


class Solution:

	def letterCombinations(self, digits):
		key = {2: 'abc', 3: 'def', 4: 'ghi', 5: 'jkl', 6: 'mno', 7: 'pqrs', 8: 'tuv', 9: 'wxyz'}
		nonlocal out
		out = ['']

		def eachLetter(i):
			if i < len(digits):
				nonlocal out
				if int(digits[i]) > 1:
					x = []
					for j in out:
						for k in key[int(digits[i])]:
							x.append(j + k)
					out = x
				eachLetter(i + 1)
		eachLetter(0)
		return [] if out[0] is '' else out


class Solution:
	Dmap = {'2': 'abc', '3': 'def', '4': 'ghi', '5': 'jkl', '6': 'mno', '7': 'pqrs', '8': 'tuv', '9': 'wxyz'}

	def letterCombinations(self, digits):
		if '1' in digits or '0' in digits:
			return []
		if len(digits) == 0:
			return []
		return self.letterC(digits)

	def letterC(self, digits):
		if len(digits) == 0:
			return ['']
		res = []
		for back in self.letterC(digits[1:]):
			for fr in self.Dmap[digits[0]]:
				res.append(fr + back)
		return res


class Solution:

	def letterCombinations(self, digits):
		self.dic = {'2': 'abc', '3': 'def', '4': 'ghi', '5': 'jkl', '6': 'mno', '7': 'pqrs', '8': 'tuv', '9': 'wxyz'}
		if not digits:
			return []
		res = []
		self.dfs(digits, 0, '', res)
		return res

	def dfs(self, digits, index, path, res):
		if len(path) == len(digits):
			res.append(path)
			return
		for i in range(len(self.dic[digits[index]])):
			path_ = path + self.dic[digits[index]][i]
			self.dfs(digits, index + 1, path_, res)


class Solution:

	def __init__(self):
		self.phone = ['', '', 'abc', 'def', 'ghi', 'jkl', 'mno', 'pqrs', 'tuv', 'wxyz']

	def letterCombinations(self, digits):
		if not digits:
			return []
		results = []
		self.dfs(digits, results, '', 0)
		return results

	def dfs(self, digits, results, string, index):
		if index == len(digits):
			results.append(string)
		else:
			letters = self.phone[int(digits[index])]
			for i in range(0, len(letters)):
				self.dfs(digits, results, string + letters[i], index + 1)


class Solution:

	def letterCombinations(self, digits):
		interpret_digit = {'1': '', '2': 'abc', '3': 'def', '4': 'ghi', '5': 'jkl', '6': 'mno', '7': 'pqrs', '8': 'tuv', '9': 'wxyz', '0': ' '}
		all_combinations = [''] if digits else []
		for digit in digits:
			current_combinations = list()
			for letter in interpret_digit[digit]:
				for combination in all_combinations:
					current_combinations.append(combination + letter)
			all_combinations = current_combinations
		return all_combinations