9.31
Algorithm
Use backtracking: at each position choose every letter that can replace the current digit, append it to the partial word and recurse; when the end of the digit string is reached, output the built word.
Telephone mapping
{
'2':'ABC','3':'DEF','4':'GHI','5':'JKL',
'6':'MNO','7':'PQRS','8':'TUV','9':'WXYZ',
'1':'', '0':' ' # 1→no letters, 0→space
}
Pseudocode
backtrack(pos, word):
if pos == len(digits): output(word); return
for ch in map[digits[pos]] (empty ⇒ skip):
backtrack(pos+1, word+ch)
Python sample
pad = {'2':'ABC','3':'DEF','4':'GHI','5':'JKL','6':'MNO',
'7':'PQRS','8':'TUV','9':'WXYZ','1':'','0':' '}
def words(digits):
res = []
def dfs(i, cur):
if i == len(digits):
res.append(cur)
return
letters = pad.get(digits[i], '')
if letters == '': # digit 1
dfs(i+1, cur)
else:
for c in letters:
dfs(i+1, cur+c)
dfs(0, '')
return res
# example
print(words('145345'))
Complexity: O(kⁿ) time to generate k letters per digit over n digits, O(n) auxiliary space aside from the output list.
Back to
Chapter 9
