Published on

The Algorithm Design Manual (3rd) Exercise Solution 'E3-9'

Table of Contents

Introduction

This series is my solutions for algorithm exercises in'The Algorithm Design Manual' 3rd edition.
It's my solutions, not model answers, so if you find some mistakes or more sophisticated solutions, please post in comment area below.

Repository

Here

Exercise 3-9

Question

Write a function which, given a sequence of digits 2–9 and a dictionary of n words, reports all words described by this sequence when typed in on a standard telephone keypad. For the sequence 269 you should return any, box, boy, and cow, among other words.

Solution

Prodecure Pseudocode:

Repeat_words(arguments: [array]sequence_digits)
    Let results=array
    Copy sequence_digits into new_seq
    Call Helper_function("", new_seq)
    Return results

Helper_function(arguments: prev_string, [array]seq_rest)
    If seq_rest is empty:
        Look up prev_string in the word dictionary
        If it hits, push prev_string into results
        Return
    Pick a head element of seq_rest as n
    Delete the head element from seq_rest
    chars=Get_chars(n)
    For each c of chars do:
        Copy seq_rest into new_seq
        Helper_function(prev_string+c, new_seq)

Get_chars(arguments: n)
    Let 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],
    }
    Return dic[n]