Given a keypad as shown in the diagram, and an N digit number which is represented by array a[ ], the task is to list all words which are possible by pressing these numbers.
Example 1:
Input: N = 3, a[] = {2, 3, 4}
Output:
adg adh adi aeg aeh aei afg afh afi 
bdg bdh bdi beg beh bei bfg bfh bfi 
cdg cdh cdi ceg ceh cei cfg cfh cfi 
Explanation: When we press 2,3,4 then 
adg, adh, adi, ... cfi are the list of 
possible words.
Example 2:
Input: N = 3, a[] = {3, 4, 5}
Output:
dgj dgk dgl dhj dhk dhl dij dik dil 
egj egk egl ehj ehk ehl eij eik eil 
fgj fgk fgl fhj fhk fhl fij fik fil
Explanation: When we press 3,4,5 then 
dgj, dgk, dgl, ... fil are the list of 
possible words.
Your Task:
You don't need to read input or print anything. You just need to complete the function possibleWords() that takes an array a[ ] and N as input parameters and returns an array of all the possible words in lexicographical increasing order. 
Expected Time Complexity: O(4^{N}^{ }* N).
Expected Auxiliary Space: O(N).
Constraints:
1 ≤ N ≤ 10
2 ≤ a[i] ≤ 9

Difficulty: MEDIUM
Tags: String algorithms

Data structures

Mathematics

Complete search
Skill types: Data structures

Complete search
Expected Time Complexity: O(4^{N}^{ }* N).
Expected Auxiliary Space: O(N).

Starter code:
#User function Template for python3


class Solution:
    
    #Function to find list of all words possible by pressing given numbers.
    def possibleWords(self,a,N):
        #Your code here

Solutions:
class Solution:

	def possibleWords(self, a, N):
		self.digit_map = {2: 'abc', 3: 'def', 4: 'ghi', 5: 'jkl', 6: 'mno', 7: 'pqrs', 8: 'tuv', 9: 'wxyz'}
		self.ans = []

		def recursion(a, index, ds):
			if index == len(a):
				self.ans.append(ds)
				return
			for ch in self.digit_map[a[index]]:
				recursion(a, index + 1, ds + ch)
		recursion(a, 0, '')
		return self.ans


class Solution:

	def genstrings(self, arr, index, string):
		if index == len(arr):
			self.res.append(string)
			return
		for char in self.mapping[arr[index]]:
			self.genstrings(arr, index + 1, string + char)

	def possibleWords(self, a, N):
		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.res = []
		self.genstrings(a, 0, '')
		return self.res


class Solution:

	def possibleWords(self, a, N):

		def rec(ind, a, N, curr, res):
			if ind == N:
				res.append(curr)
				return
			val = a[ind]
			lett = d[val]
			for alph in lett:
				curr += alph
				rec(ind + 1, a, N, curr, res)
				curr = curr[:-1]
		d = {2: 'abc', 3: 'def', 4: 'ghi', 5: 'jkl', 6: 'mno', 7: 'pqrs', 8: 'tuv', 9: 'wxyz'}
		res = []
		rec(0, a, N, '', res)
		return res


def solve(a, output, index, ans, mapping):
	if index >= len(a):
		ans.append(output)
		return
	number = a[index]
	value = mapping[number]
	for i in range(len(value)):
		output += value[i]
		solve(a, output, index + 1, ans, mapping)
		output = output[:len(output) - 1]

class Solution:

	def possibleWords(self, a, N):
		ans = []
		output = ''
		index = 0
		mapping = ['', '', 'abc', 'def', 'ghi', 'jkl', 'mno', 'pqrs', 'tuv', 'wxyz']
		solve(a, output, index, ans, mapping)
		return ans


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

class Solution:

	def possibleWords(self, a, N):
		num = ''
		for i in a:
			num += str(i)
		ans = self.combo(num)
		return ans

	def combo(self, phnum):
		if len(phnum) == 1:
			return list(numbs[phnum[0]])
		else:
			result = self.combo(phnum[:-1])
		return [ch1 + ch2 for ch1 in result for ch2 in numbs[phnum[-1]]]


class Solution:

	def possibleWords(self, a, N):
		output = []
		d = {2: 'abc', 3: 'def', 4: 'ghi', 5: 'jkl', 6: 'mno', 7: 'pqrs', 8: 'tuv', 9: 'wxyz'}

		def helper(ind, cur):
			if ind == N:
				output.append(cur)
				return
			for i in d[a[ind]]:
				helper(ind + 1, cur + i)
		helper(0, '')
		return output


class Solution:

	def possibleWords(self, a, N):
		ans = ''
		res = []
		dirc = {1: [], 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']}

		def getAns(ind, ans, res, dirc):
			if ind == N:
				res.append(ans)
				return
			num = a[ind]
			lett = dirc[num]
			for i in lett:
				ans += i
				getAns(ind + 1, ans, res, dirc)
				ans = ans[:-1]
		getAns(0, ans, res, dirc)
		return res


class Solution:

	def possibleWords(self, a, N):
		d = {2: 'abc', 3: 'def', 4: 'ghi', 5: 'jkl', 6: 'mno', 7: 'pqrs', 8: 'tuv', 9: 'wxyz'}
		res = []

		def backtrack(i, curr):
			if i >= N:
				res.append(curr)
				return
			keyval = d[a[i]]
			for j in keyval:
				curr += j
				backtrack(i + 1, curr)
				curr = curr[:-1]
		backtrack(0, '')
		return res


class Solution:

	def possibleWords(self, a, N):
		arr = [[], [], ['a', 'b', 'c'], ['d', 'e', 'f'], ['g', 'h', 'i'], ['j', 'k', 'l'], ['m', 'n', 'o'], ['p', 'q', 'r', 's'], ['t', 'u', 'v'], ['w', 'x', 'y', 'z']]
		sub = ''
		res = []
		self.func(a, N, arr, sub, 0, res)
		return res

	def func(self, a, n, arr, sub, k, res):
		if k == n:
			res.append(sub)
		else:
			self.func(a, n, arr, sub + arr[a[k]][0], k + 1, res)
			self.func(a, n, arr, sub + arr[a[k]][1], k + 1, res)
			self.func(a, n, arr, sub + arr[a[k]][2], k + 1, res)
			if a[k] == 7 or a[k] == 9:
				self.func(a, n, arr, sub + arr[a[k]][3], k + 1, res)


keypad = ['', '', 'abc', 'def', 'ghi', 'jkl', 'mno', 'pqrs', 'tuv', 'wxyz']

class Solution:

	def possibleWords(self, a, N):

		def helper(i, w, res, a, N):
			if i == N:
				res.append(w)
				return
			for j in range(len(keypad[a[i]])):
				helper(i + 1, w + keypad[a[i]][j], res, a, N)
		res = []
		helper(0, '', res, a, N)
		return res


class Solution:

	def keypad_combinations(self, a, keypad, index, word, result):
		if index == len(a):
			result.append(word)
			return
		for letter in keypad[a[index]]:
			self.keypad_combinations(a, keypad, index + 1, word + letter, result)

	def possibleWords(self, a, N):
		keypad = {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']}
		result = []
		self.keypad_combinations(a, keypad, 0, '', result)
		return result


class Solution:

	def possibleWords(self, a, N):
		hash = ['.', 'abc', 'def', 'ghi', 'jkl', 'mno', 'pqrs', 'tuv', 'wxyz']

		def comb(index, n, str, out, ll):
			if index == n:
				ll.append(out)
				return ll
			tt = hash[str[index] - 1]
			for i in range(len(tt)):
				k = out
				val = hash[str[index] - 1]
				out += val[i]
				ll = comb(index + 1, n, str, out, ll)
				out = k
			return ll
		lis = comb(0, N, a, '', [])
		lis.sort()
		return lis


class Solution:

	def possibleWords(self, a, N):
		d = {2: 'abc', 3: 'def', 4: 'ghi', 5: 'jkl', 6: 'mno', 7: 'pqrs', 8: 'tuv', 9: 'wxyz'}
		ans = ['']
		for r in range(N):
			ans = [i + j for j in d[a[r]] for i in ans]
		return sorted(ans)


class Solution:

	def possibleWords(self, a, N):
		keymap = ['', '', 'abc', 'def', 'ghi', 'jkl', 'mno', 'pqrs', 'tuv', 'wxyz']
		output = []

		def recursive(curr=0, word=''):
			if curr == N:
				return output.append(word)
			for i in range(len(keymap[a[curr]])):
				word = word + keymap[a[curr]][i]
				recursive(curr + 1, word)
				word = word[:-1]
			if a[curr] == 1:
				recursive(curr + 1, word)
		recursive()
		return output


class Solution:

	def possibleWords(self, a, N):

		def calc(ind, s):
			if ind == N:
				ans.append(s)
				return
			for i in dic[a[ind]]:
				s += i
				calc(ind + 1, s)
				s = s[:-1]
		ans = []
		dic = ['', '', 'abc', 'def', 'ghi', 'jkl', 'mno', 'pqrs', 'tuv', 'wxyz']
		calc(0, '')
		return ans


class Solution:

	def possibleWords(self, a, N):
		arr = ['', '', 'abc', 'def', 'ghi', 'jkl', 'mno', 'pqrs', 'tuv', 'wxyz']
		output = ''
		ans = []
		ind = 0

		def find(ind, cur, output, ans, a, arr):
			if cur == N:
				ans.append(output)
				return
			for i in range(len(arr[a[cur]])):
				val = arr[a[cur]][i]
				output = output + val
				find(ind, cur + 1, output, ans, a, arr)
				output = output[0:-1]
				if a[cur] == 0 or a[cur] == 1:
					return
		find(0, 0, output, ans, a, arr)
		return ans


class Solution:

	def possibleWords(self, a, N):

		def helper(cur, ind, a, N, res, mapp):
			if ind == N:
				res.append(cur)
				return res
			for i in mapp[a[ind]]:
				helper(cur + i, ind + 1, a, N, res, mapp)
		mapp = {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']}
		res = []
		helper('', 0, a, N, res, mapp)
		res.sort()
		return res


class Solution:

	def possibleWords(self, a, N):
		ans = []
		d = {2: 'abc', 3: 'def', 4: 'ghi', 5: 'jkl', 6: 'mno', 7: 'pqrs', 8: 'tuv', 9: 'wxyz'}

		def solve(ind, s):
			if ind == N:
				ans.append(s)
				return
			for i in d[a[ind]]:
				solve(ind + 1, s + i)
		solve(0, '')
		return ans


class Solution:

	def possibleWords(self, a, N):
		di = {2: 'abc', 3: 'def', 4: 'ghi', 5: 'jkl', 6: 'mno', 7: 'pqrs', 8: 'tuv', 9: 'wxyz'}

		def f(ind, s):
			if ind == N:
				l.append(s)
				return
			for i in di[a[ind]]:
				f(ind + 1, s + i)
		l = []
		if a:
			f(0, '')
			return l


class Solution:

	def util(self, a, d, i, n, ans):
		global fans
		if i == n:
			fans.append(ans)
			return
		for j in d[a[i]]:
			self.util(a, d, i + 1, n, ans + j)

	def possibleWords(self, a, N):
		global fans
		fans = []
		d = {2: 'abc', 3: 'def', 4: 'ghi', 5: 'jkl', 6: 'mno', 7: 'pqrs', 8: 'tuv', 9: 'wxyz'}
		self.util(a, d, 0, N, '')
		return fans


class Solution:

	def __init__(self):
		self.phone = {1: [], 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'], 0: []}

	def possibleWords(self, a, N):
		self.n = N
		return self.generate(0, a, '', [])

	def generate(self, i, a, message, ans):
		if i == self.n:
			ans.append(message)
			return ans
		letters = self.phone[a[i]]
		if letters:
			for j in range(len(letters)):
				ans = self.generate(i + 1, a, message + letters[j], ans)
		else:
			ans = self.generate(i + 1, a, message, ans)
		return ans


class Solution:

	def helper(self, index, a, N, curr, d, res):
		if index == N:
			res.append(curr)
			return
		val = a[index]
		word = d[val]
		for letter in word:
			curr += letter
			self.helper(index + 1, a, N, curr, d, res)
			curr = curr[:-1]
		return res

	def possibleWords(self, a, N):
		d = {2: 'abc', 3: 'def', 4: 'ghi', 5: 'jkl', 6: 'mno', 7: 'pqrs', 8: 'tuv', 9: 'wxyz'}
		res = []
		self.helper(0, a, N, '', d, res)
		return res


class Solution:

	def helper(self, N, curr, i, l):
		if N == i:
			l.append(curr)
			return
		if len(keys[i]) == 3:
			self.helper(N, curr + keys[i][0], i + 1, l)
			self.helper(N, curr + keys[i][1], i + 1, l)
			self.helper(N, curr + keys[i][2], i + 1, l)
		else:
			self.helper(N, curr + keys[i][0], i + 1, l)
			self.helper(N, curr + keys[i][1], i + 1, l)
			self.helper(N, curr + keys[i][2], i + 1, l)
			self.helper(N, curr + keys[i][3], i + 1, l)

	def get_keys(self, a):
		d = {2: 'abc', 3: 'def', 4: 'ghi', 5: 'jkl', 6: 'mno', 7: 'pqrs', 8: 'tuv', 9: 'wxyz'}
		keys = []
		for k in a:
			keys.append(d[k])
		return keys

	def possibleWords(self, a, N):
		global keys
		keys = self.get_keys(a)
		l = []
		self.helper(N=N, curr='', i=0, l=l)
		l.sort()
		return l


class Solution:

	def possibleWords(self, a, N):
		keypad = {1: [], 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']}

		def possibleWordsRec(a, N, words):
			if N == 0:
				return words
			else:
				chars = keypad[a[0]]
				words_tmp = []
				if len(words) == 0:
					words_tmp = chars
				else:
					for w in words:
						for c in chars:
							words_tmp.append(w + c)
				del a[0]
				words = words_tmp
				return possibleWordsRec(a, N - 1, words)
		result = possibleWordsRec(a, N, [])
		return result


class Solution:

	def possibleWords(self, a, N):
		res = {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']}

		def recurs(i, vals):
			nonlocal result
			if len(vals) == N:
				result.append(''.join(vals.copy()))
				return
			for x in res[a[i]]:
				recurs(i + 1, vals + [x])
		result = []
		recurs(0, [])
		return sorted(result)


class Solution:

	def possibleWords(self, a, N):
		characters = 'abcdefghijklmnopqrstuvwxyz'
		st = 0
		numToLetters = {}
		for i in range(2, 10):
			if i == 7 or i == 9:
				ed = st + 4
			else:
				ed = st + 3
			numToLetters[i] = [st, ed]
			st = ed
		self.pool = a
		self.possibilities = []
		self.word = ''
		self.numToLetters = numToLetters
		self.characters = characters
		self.populate()
		return self.possibilities

	def populate(self, idx=0, word=''):
		(st, ed) = self.numToLetters[self.pool[idx]]
		for char in self.characters[st:ed]:
			myword = word + char
			if idx == len(self.pool) - 1:
				self.possibilities.append(myword)
			else:
				self.populate(idx + 1, myword)
		return


class Solution:

	def possibleWords(self, a, N):
		ans = []

		def create(idx, temp):
			if idx == N:
				ans.append(temp)
				return
			for c in m[a[idx]]:
				create(idx + 1, temp + c)
		m = {2: 'abc', 3: 'def', 4: 'ghi', 5: 'jkl', 6: 'mno', 7: 'pqrs', 8: 'tuv', 9: 'wxyz'}
		create(0, '')
		return ans


class Solution:

	def possibleWords(self, a, N):
		ans = []
		arr = []
		digmap = dict()
		digmap[2] = ['a', 'b', 'c']
		digmap[3] = ['d', 'e', 'f']
		digmap[4] = ['g', 'h', 'i']
		digmap[5] = ['j', 'k', 'l']
		digmap[6] = ['m', 'n', 'o']
		digmap[7] = ['p', 'q', 'r', 's']
		digmap[8] = ['t', 'u', 'v']
		digmap[9] = ['w', 'x', 'y', 'z']

		def funcall(index, arr):
			if index == N:
				ans.append(''.join(arr))
				return
			for char in digmap[a[index]]:
				arr.append(char)
				funcall(index + 1, arr)
				arr.pop()
		funcall(0, arr)
		if ans == ['']:
			return []
		return ans


class Solution:

	def possibleWords(self, a, N):
		m = {'2': 'abc', '3': 'def', '4': 'ghi', '5': 'jkl', '6': 'mno', '7': 'pqrs', '8': 'tuv', '9': 'wxyz'}
		phnum = ''
		for i in a:
			phnum += str(i)

		def combinations(phnum):
			if len(phnum) == 1:
				return list(m[phnum])
			result1 = combinations(phnum[:-1])
			result2 = m[phnum[-1]]
			return [ch1 + ch2 for ch1 in result1 for ch2 in result2]
		return combinations(phnum)


class Solution:

	def possibleWords(self, a, N):
		phone_dict = {2: 'abc', 3: 'def', 4: 'ghi', 5: 'jkl', 6: 'mno', 7: 'pqrs', 8: 'tuv', 9: 'wxyz'}
		arr = [phone_dict[i] for i in a]

		def phone_digit(n, arr, output, container):
			if n == 0:
				container.append(output)
				return
			for i in range(len(arr[0])):
				phone_digit(n - 1, arr[1:], output + arr[0][i], container)
			arr.pop(0)
			return
		container = []
		phone_digit(N, arr, '', container)
		return container


class Solution:

	def possibleWords(self, arr, N):
		hm = {1: '', 2: 'abc', 3: 'def', 4: 'ghi', 5: 'jkl', 6: 'mno', 7: 'pqrs', 8: 'tuv', 9: 'wxyz', 10: '*', 11: '0', 12: '#'}
		ans = []

		def solve(i, curr):
			if i == N:
				ans.append(''.join(curr.copy()))
				return
			key = arr[i]
			for ch in hm[key]:
				curr.append(ch)
				solve(i + 1, curr)
				curr.pop()
		solve(0, [])
		return ans


class Solution:

	def possibleWords(self, a, N):
		keypad = {2: 'abc', 3: 'def', 4: 'ghi', 5: 'jkl', 6: 'mno', 7: 'pqrs', 8: 'tuv', 9: 'wxyz'}

		def generate_list(list_to_be_generated, keypad, number):
			if len(list_to_be_generated) == 0:
				string = keypad[number]
				for i in string:
					list_to_be_generated.append(i)
			else:
				string = keypad[number]
				newlist = []
				for i in string:
					for j in range(len(list_to_be_generated)):
						newlist.append(list_to_be_generated[j] + i)
				list_to_be_generated = newlist
			return list_to_be_generated
		generated_list = []
		for number in range(N):
			generated_list = generate_list(generated_list, keypad, a[number])
		return sorted(generated_list)


class Solution:

	def possibleWords(self, a, N):
		all = {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']}
		ret = []
		for d in a:
			if len(ret) == 0:
				ret = all[d]
			else:
				copy = []
				for r in ret:
					for a in all[d]:
						copy.append(r + a)
				ret = copy
		return ret


class Solution:

	def hell(self, a, i, N, cur, dic, res):
		if len(cur) == len(a):
			res.append(cur)
			return
		x = dic.get(a[i])
		for j in x:
			cur = cur + j
			Solution.hell(self, a, i + 1, N, cur, dic, res)
			cur = cur[:len(cur) - 1]
		return res

	def possibleWords(self, a, N):
		cur = ''
		res = []
		dic = {2: 'abc', 3: 'def', 4: 'ghi', 5: 'jkl', 6: 'mno', 7: 'pqrs', 8: 'tuv', 9: 'wxyz'}
		return Solution.hell(self, a, 0, N, cur, dic, res)


class Solution:

	def helper(self, input_arr, n, temp, idx, result, button_arr):
		if idx == n:
			result.append(temp)
			return
		j = 0
		while j < len(button_arr[input_arr[idx]]):
			self.helper(input_arr, n, temp + button_arr[input_arr[idx]][j], idx + 1, result, button_arr)
			j += 1

	def possibleWords(self, a, N):
		result = []
		button_arr = ['', '', 'abc', 'def', 'ghi', 'jkl', 'mno', 'pqrs', 'tuv', 'wxyz']
		self.helper(a, N, '', 0, result, button_arr)
		return result


class Solution:

	def possibleWords(self, a, N):
		res = []
		self.func(a, N, 0, res, '')
		return res

	def func(self, a, N, index, res, s):
		if index == N:
			if len(s) > 0:
				res.append(s)
			return res
		temp = a[index]
		if temp == 0 or temp == 1:
			self.func(a, N, index + 1, res, s)
			return res
		mob = [[], [], ['a', 'b', 'c'], ['d', 'e', 'f'], ['g', 'h', 'i'], ['j', 'k', 'l'], ['m', 'n', 'o'], ['p', 'q', 'r', 's'], ['t', 'u', 'v'], ['w', 'x', 'y', 'z']]
		temp_str = s
		for i in range(len(mob[temp])):
			s += mob[temp][i]
			self.func(a, N, index + 1, res, s)
			s = temp_str
		return res


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

	def possibleWords(self, a, N):
		res = []
		self.possibleWordsHelper(a, N, 0, '', res)
		res.sort()
		return res

	def possibleWordsHelper(self, a, N, i, s, res):
		if i == N:
			res.append(s)
			return
		chars = list(self.wordmap.get(a[i]))
		for c in chars:
			self.possibleWordsHelper(a, N, i + 1, s + c, res)


class Solution:

	def possibleWords(self, a, N):
		d = {1: '', 2: 'abc', 3: 'def', 4: 'ghi', 5: 'jkl', 6: 'mno', 7: 'pqrs', 8: 'tuv', 9: 'wxyz'}
		ans = []
		w = ''
		for i in a:
			w = w + str(i)

		def poss(out, ind):
			if ind == len(w):
				ans.append(out)
				return
			curr_ind = int(w[ind])
			word = d[curr_ind]
			for i in word:
				poss(out + i, ind + 1)
		poss('', 0)
		return ans


class Solution:

	def possibleWords(self, a, N):
		codes = ['', '', 'abc', 'def', 'ghi', 'jkl', 'mno', 'pqrs', 'tuv', 'wxyz']
		if len(a) == 0:
			res = []
			res.append('')
			return res
		ch = a[0]
		ros = a[1:]
		rres = self.possibleWords(ros, N)
		code_val = codes[ch]
		mres = []
		for i in code_val:
			for r in rres:
				mres.append(i + r)
		return mres


from itertools import product

class Solution:

	def possibleWords(self, a, N):
		dict = {'2': 'abc', '3': 'def', '4': 'ghi', '5': 'jkl', '6': 'mno', '7': 'pqrs', '8': 'tuv', '9': 'wxyz'}
		if not a:
			return []
		lst = []
		for i in a:
			i = str(i)
			if i in dict:
				lst.append(dict[i])
		ans = product(*lst)
		res = []
		for i in ans:
			res.append(''.join(i))
		return res


class Solution:

	def possibleWords(self, a, N):

		def numb(s1, s2):
			x = []
			for i in d[s1]:
				for j in d[s2]:
					y = i + j
					x.append(y)
			d[s1 + s2] = x
			return s1 + s2
		d = {'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']}
		strr = ''
		for e in a:
			strr = strr + str(e)
		if len(strr) == 2:
			x = numb(strr[0], strr[1])
		elif len(strr) == 1:
			return d[strr]
		else:
			x = numb(strr[0], strr[1])
			for i in range(2, len(strr)):
				x = numb(x, strr[i])
		return d[x]


class Solution:

	def __init__(self):
		self.arr = [[] for _ in range(13)]
		self.arr[2] = ['a', 'b', 'c']
		self.arr[3] = ['d', 'e', 'f']
		self.arr[4] = ['g', 'h', 'i']
		self.arr[5] = ['j', 'k', 'l']
		self.arr[6] = ['m', 'n', 'o']
		self.arr[7] = ['p', 'q', 'r', 's']
		self.arr[8] = ['t', 'u', 'v']
		self.arr[9] = ['w', 'x', 'y', 'z']

	def solve(self, arr, start, N, ans, store):
		if start >= N:
			store.append(ans)
			return
		for i in self.arr[arr[start]]:
			self.solve(arr, start + 1, N, ans + i, store)

	def possibleWords(self, arr, N):
		store = []
		self.solve(arr, 0, N, '', store)
		return store


class Solution:

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

	def prepare_words_phone_digits(self, l, ch_str):
		if len(l) == 1:
			for ch in l[0]:
				self.char_list.append(ch_str + ch)
		elif len(l) >= 2:
			for ch in l[0]:
				self.prepare_words_phone_digits(l[1:], ch_str + ch)

	def possibleWords(self, a, N):
		l = []
		for i in a:
			l.append(self.list_numbers[i - 1])
		self.prepare_words_phone_digits(l, '')
		return self.char_list


class Solution:

	def possibleWords(self, a, N):
		return phn(a, N)

def phn(a, N):
	res = []
	alphamap = {2: 'abc', 3: 'def', 4: 'ghi', 5: 'jkl', 6: 'mno', 7: 'pqrs', 8: 'tuv', 9: 'wxyz'}

	def bt(i, curr, N):
		if len(curr) == N:
			res.append(curr)
			return
		for c in alphamap[a[i]]:
			bt(i + 1, curr + c, N)
	bt(0, '', N)
	return res


def solve(a, output, ans, d, index, N):
	if index == N:
		s = ''.join(output[:])
		ans.append(s)
		return ans
	num = a[index]
	value = d[num]
	for i in range(len(value)):
		output.append(value[i])
		solve(a, output, ans, d, index + 1, N)
		output.pop(-1)

class Solution:

	def possibleWords(self, a, N):
		ans = []
		d = dict()
		d = {0: '', 1: '', 2: 'abc', 3: 'def', 4: 'ghi', 5: 'jkl', 6: 'mno', 7: 'pqrs', 8: 'tuv', 9: 'wxyz'}
		output = []
		solve(a, output, ans, d, 0, N)
		return ans


class Solution:

	def possibleWords(self, arr, N):
		d = {2: 'abc', 3: 'def', 4: 'ghi', 5: 'jkl', 6: 'mno', 7: 'pqrs', 8: 'tuv', 9: 'wxyz'}
		o = []

		def recurr(d, i, out, arr, o):
			if i == len(arr):
				o.append(''.join(out))
				return
			for j in range(len(d[arr[i]])):
				if arr[i] == 1 or arr[i] == 0:
					return
				recurr(d, i + 1, out + [d[arr[i]][j]], arr, o)
		recurr(d, 0, [], arr, o)
		return o


class Solution:
	_dict = {1: (), 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')}

	def possibleWords(self, a, N):
		ls = []
		self.helper(a, N, 0, '', ls)
		return ls

	def helper(self, a, N, idx, op_str, ls):
		if idx == N:
			ls.append(op_str)
			return
		chars = self._dict[a[idx]]
		for ch in chars:
			self.helper(a, N, idx + 1, op_str + ch, ls)


class Solution:

	def __init__(self):
		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.strings = []

	def recursive_string_builder(self, str1, keys):
		if keys == []:
			self.strings.append(str1)
			return
		else:
			x = keys.pop(0)
			for i in self.mapping.get(x):
				self.recursive_string_builder(str1 + i, keys.copy())

	def possibleWords(self, a, N):
		self.recursive_string_builder('', a)
		return self.strings


class Solution:

	def possibleWords(self, a, n):
		b = []
		ans = []
		ind_max = []
		ind = [0 for i in range(n)]
		fac = [1 for i in range(n)]
		for i in range(n):
			if a[i] == 2:
				s = 'abc'
			elif a[i] == 3:
				s = 'def'
			elif a[i] == 4:
				s = 'ghi'
			elif a[i] == 5:
				s = 'jkl'
			elif a[i] == 6:
				s = 'mno'
			elif a[i] == 7:
				s = 'pqrs'
			elif a[i] == 8:
				s = 'tuv'
			elif a[i] == 9:
				s = 'wxyz'
			b.append(s)
			ind_max.append(len(s))
		f = 1
		for i in range(n - 1, 0, -1):
			if a[i] == 7 or a[i] == 9:
				fac[i - 1] = fac[i] * 4
			else:
				fac[i - 1] = fac[i] * 3
		if a[0] == 7 or a[0] == 9:
			t = fac[0] * 4
		else:
			t = fac[0] * 3
		i = 1
		while i <= t:
			p = ''
			for j in range(n):
				p += b[j][ind[j]]
			ans.append(p)
			x = n - 1
			while x >= 0:
				if i % fac[x] == 0:
					if ind[x] == ind_max[x] - 1:
						ind[x] = 0
					else:
						ind[x] += 1
				else:
					break
				x -= 1
			i += 1
		return ans


import itertools as it

class Solution:

	def possibleWords(self, a, N):
		m = {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']}
		k = [m[i] for i in a]
		l = []
		for r in list(it.product(*k)):
			l.append(''.join(r))
		return l


class Solution:

	def check(self, a, i, out, n, dic, ans):
		if i >= n:
			ans.append(''.join(out))
			return
		for j in range(len(dic[a[i]])):
			out.append(dic[a[i]][j])
			self.check(a, i + 1, out, n, dic, ans)
			out.pop()

	def possibleWords(self, a, N):
		dic = {0: '', 1: '', 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']}
		ans = []
		self.check(a, 0, [], N, dic, ans)
		return ans


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

	def possibleWords(self, a, N, i=0, permute=''):
		if N > len(a):
			N = len(a)
		if i == N - 1:
			return [permute + x for x in Solution.possible_nums[a[i]]]
		curr = Solution.possible_nums[a[i]]
		ans = []
		for j in range(len(curr)):
			ans += self.possibleWords(a, N, i + 1, permute + curr[j])
		return ans


class Solution:

	def possibleWords(self, a, n):

		def solve(index, temp, ans, s, n):
			if index == n:
				ans.append(s)
				return
			for j in temp[index]:
				s += j
				solve(index + 1, temp, ans, s, n)
				s = s[:-1]
		d = {2: 'abc', 3: 'def', 4: 'ghi', 5: 'jkl', 6: 'mno', 7: 'pqrs', 8: 'tuv', 9: 'wxyz'}
		ans = []
		temp = []
		for i in a:
			temp.append(d[i])
		s = ''
		solve(0, temp, ans, s, n)
		return ans


class Solution:

	def Phone_number(self, arr, n, i, str1, res, op):
		if i == n:
			res.append(op)
			return
		no = str1[arr[i]]
		for op1 in no:
			op1 = op + op1
			self.Phone_number(arr, n, i + 1, str1, res, op1)
			op1 = ''.join([op1[i] for i in range(len(op1) - 1)])

	def possibleWords(self, a, N):
		res = []
		str1 = ['', '', 'abc', 'def', 'ghi', 'jkl', 'mno', 'pqrs', 'tuv', 'wxyz']
		self.Phone_number(a, N, 0, str1, res, '')
		return res


class Solution:

	def possibleWords(self, a, N):
		letters = [['a', 'b', 'c'], ['d', 'e', 'f'], ['g', 'h', 'i'], ['j', 'k', 'l'], ['m', 'n', 'o'], ['p', 'q', 'r', 's'], ['t', 'u', 'v'], ['w', 'x', 'y', 'z']]
		i = 0
		ans = []
		str = ''
		self.permutation(str, a, i, N, ans, letters)
		return ans

	def permutation(self, str, a, i, N, ans, letters):
		if i == N:
			ans.append(str)
		else:
			for j in letters[a[i] - 2]:
				self.permutation(str + j, a, i + 1, N, ans, letters)


class Solution:

	def possibleWords(self, a, N):
		keys = {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')}
		res = []

		def helper(idx, temp):
			if len(temp) == N:
				res.append(temp[:])
				return
			for i in range(idx, len(a)):
				for val in keys[a[i]]:
					temp += val
					helper(i + 1, temp)
					temp = temp[:-1]
		helper(0, '')
		return res


class Solution:

	def possibleWords(self, a, N):
		c = ''
		for i in a:
			c += str(i)

		def helper(i, m):
			if i > N:
				return
			if i == N:
				new = ''
				for j in subset:
					new += j
				ans.append(new)
				return
			str = m[c[i]]
			for j in range(len(str)):
				subset.append(str[j])
				helper(i + 1, m)
				subset.pop()
		m = {'2': 'abc', '3': 'def', '4': 'ghi', '5': 'jkl', '6': 'mno', '7': 'pqrs', '8': 'tuv', '9': 'wxyz'}
		if not c:
			return []
		ans = []
		subset = []
		helper(0, m)
		return ans


class Solution:

	def possibleWords(self, a, N):
		res = []
		digg = {2: 'abc', 3: 'def', 4: 'ghi', 5: 'jkl', 6: 'mno', 7: 'pqrs', 8: 'tuv', 9: 'wxyz'}

		def back(i, curr):
			if len(curr) == len(a):
				res.append(curr)
				return
			for char in digg[a[i]]:
				back(i + 1, curr + char)
		if a:
			back(0, '')
		return res


class Solution:

	def possibleWords(self, a, N):
		digit = {2: 'abc', 3: 'def', 4: 'ghi', 5: 'jkl', 6: 'mno', 7: 'pqrs', 8: 'tuv', 9: 'wxyz'}

		def f(ind, path):
			if ind == N:
				res.append(path)
				return
			for j in digit[a[ind]]:
				path += j
				f(ind + 1, path)
				path = path[:-1]
		res = []
		f(0, '')
		return res


class Solution:

	def __init__(self):
		self.phone_dict = dict()
		self.phone_dict[2] = 'abc'
		self.phone_dict[3] = 'def'
		self.phone_dict[4] = 'ghi'
		self.phone_dict[5] = 'jkl'
		self.phone_dict[6] = 'mno'
		self.phone_dict[7] = 'pqrs'
		self.phone_dict[8] = 'tuv'
		self.phone_dict[9] = 'wxyz'
		self.arr1 = []

	def pW(self, a, N, i=0, created=''):
		if i == N:
			self.arr1.append(created)
			return
		for chr in self.phone_dict[a[i]]:
			self.pW(a, N, i + 1, created + chr)

	def possibleWords(self, a, N):
		self.pW(a, N)
		return self.arr1


class Solution:

	def possibleWords(self, arr, N):
		dictt = {2: 'abc', 3: 'def', 4: 'ghi', 5: 'jkl', 6: 'mno', 7: 'pqrs', 8: 'tuv', 9: 'wxyz'}
		res = []
		self.dfs(dictt, arr, '', res)
		return res

	def dfs(self, dictt, arr, path, res):
		if len(arr) == 0:
			res.append(path)
			return
		for e in dictt[arr[0]]:
			self.dfs(dictt, arr[1:], path + e, res)


class Solution:

	def possibleWords(self, a, N):
		ans = []
		dic = {2: 'abc', 3: 'def', 4: 'ghi', 5: 'jkl', 6: 'mno', 7: 'pqrs', 8: 'tuv', 9: 'wxyz'}

		def helper(i, a, N):
			if i == N:
				return ['']
			ans = helper(i + 1, a, N)
			output = []
			for child in dic[a[i]]:
				for ele in ans:
					output.append(child + ele)
			return output
		return helper(0, a, N)