Question: Given a finite number, find out all the possible strings that can be generated by using encoding found on old telephone keypad.

Example: 223 => bad, bae, aae...etc. ( since 2 = abc , 3 = def ... )

Answer: This is a simple recursion problem. We should recurse the loop for each possible character of every digit in given number and append the character to the output. As soon as output length is equal to the input length process/print it.

A small trick is to properly choose function argument, which should allow us to check the current length of the o/p and also the number of characters for current digits.

Code: Ruby code


#!usr/bin/ruby

$array = [" ", " ", "abc", "def", "ghi", "jkl", "mno", "pqrs", "tuv", "wxyz"]

def find_comb(input, length, index, out)
if index == length
    print out
    print "\n"
    return
end

for j in 0..($array[input[index].to_i].length-1)
    out[index] = $array[input[index].to_i][j]
    find_comb(input, length, index+1, out)
end


end

if ARGV[0].index('1') or ARGV[0].index('0')
  p "0 and 1 are not allowed."
  p "Syntax: ruby telephone.rb number"
  exit
end

find_comb(ARGV[0], ARGV[0].length, 0, "")

Complexity: If we assume that every number on keypad has 3 letters (actually 7 and 9 has 4 words each) then possible number of words are 3^n. Since we are processing every word just once, our algorithm complexity is also O(3^n).

PS: Follow-up to this question might be to remove duplicate in the output generated.
or
To show only the dictionary words in output.

Subscribe - To get an automatic feed of all future posts subscribe here, or to receive them via email go here and enter your email address in the box. You can also like us on facebook and follow me on Twitter @akashag1001.