# Phone number to words based on the dictionary

This is the problem:

Given a 10 digit phone number, you must return all possible words or combination of words from the provided dictionary, that can be mapped back as a whole to the number.

With this we can generate numbers like 1-800-motortruck which is easier to remember then 1-800-6686787825

The phone number mapping to letters is as follows:

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


The phone numbers will never contain a 0 or 1. Words have to be at least 3 characters.

To get give you an initial verifiation, the following must be true:

• 6686787825 should return the following list [["motor", "usual"], ["noun", "struck"], ["nouns", "truck"], ["nouns", "usual"], ["onto", "struck"], "motortruck"] # These words exist in a dictionary file.

• The conversion of a 10 digit phone number should be performed within 1000ms.

My solution works but takes longer than 1 sec. How can I improve my code so execution time will be less than 1 sec?

class NumberToWord

def letter_combinations(digits)
#return if number not valid
return [] if digits.nil? || digits.length != 10 || digits.split('').select{|a|(a.to_i == 0 || a.to_i == 1)}.length > 0
#number to letters mapping
letters = {"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"]}

# Read dictionary file and hold all values in a array
dictionary = []
file_path = "dictionary.txt"
File.foreach( file_path ) do |word|
dictionary.push word.chop.to_s.downcase
end
# get all letters for numbers in form of array
keys = digits.chars.map{|digit|letters[digit]}

results = {}
total_number = keys.length - 1 # total numbers
#Loo through all letters and get matching records with dictionary
for i in (2..total_number)
first_array = keys[0..i]
second_array = keys[i + 1..total_number]
next if first_array.length < 3 || second_array.length < 3
first_combination = first_array.shift.product(*first_array).map(&:join) # Get product of arrays
next if first_combination.nil?
second_combination = second_array.shift.product(*second_array).map(&:join)
next if second_combination.nil?
results[i] = [(first_combination & dictionary), (second_combination & dictionary)] # get common values from arrays
end
#arrange words like we need as a output
final_words = []
results.each do |key, combinataions|
next if combinataions.first.nil? || combinataions.last.nil?
combinataions.first.product(combinataions.last).each do |combo_words|
final_words << combo_words
end
end
# for all numbers
final_words << (keys.shift.product(*keys).map(&:join) & dictionary).join(", ") # matche with all character
final_words
end

end

final_words = NumberToWord.new().letter_combinations("6686787825")
print final_words

• Where can we find the dictionary file, if we want to try this out? Mar 21 '17 at 12:11
• @Flambino can you please let me know any common place where I can put that dictionary, or just give me your email address so I can send it to you Mar 22 '17 at 4:46
• this is the file: github.com/ansarmirza/assignment/blob/master/db/dictionary.txt Mar 22 '17 at 4:48
• Please don't edit your main question due to feedback you've received. Feel free to post a new question with your new code, if you feel like there's more you can improve.
– user95591
Mar 30 '17 at 14:56
• Sorry that was edit by mistake, I have added the same thing again Mar 30 '17 at 14:57

I would first start by doing some basic profiling of your application to see where the issues are. This could be as simple as inserting console.log( (new Date()).valueOf() ) in a few places.

Some things I noticed.

• Is your dictionary file sorted? If not then sort it first. Either way use bsearch to locate entries rather han using & which is very naive.

• It looks like you are trying every combination of letters but you probably want to use an algorithm that stops if there is no match. For example given 668, if your dictionary contains no entries starting with mn (66) then there is no point in checking mnt, mnu, mnv or any of the longer combinations.

• Try to reduce the number of times you copy and modify arrays ([a..b] or shift)

• This check: next if first_array.length < 3 || second_array.length < 3 could go before you copy the array (in a slightly modified form). You could just change for i in (2..total_number) to for i in (4..total_number-2)

• Yes dictionary is sorted Mar 22 '17 at 4:42
• As I said there are two steps: (1) Do prefix truncation. A 10 digit number has approximately 60,000 possibilities in the form of a branching tree, but if you have no words starting with the first digit, or two, or three you should stop searching that branch. (2) Use bsearch to search your dictionary. Mar 22 '17 at 16:03

Here is the optimised solution but still looking for how to write good code, I am now able to get result in 0.4 seconds:

require 'date'

class NumberToWordOpt

def letter_combinations(digits)
time_start = Time.now()
#return if number not valid
return [] if digits.nil? || digits.length != 10 || digits.split('').select{|a|(a.to_i == 0 || a.to_i == 1)}.length > 0
#number to letters mapping
letters = {"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"]}

# Read dictionary file and hold all values in a array
dictionary = {}
for i in (1..30)
dictionary[i] = []
end
file_path = "dictionary.txt"
File.foreach( file_path ) do |word|
dictionary[word.length] << word.chop.to_s.downcase
end

keys = digits.chars.map{|digit|letters[digit]}

results = {}
total_number = keys.length - 1 # total numbers
#Loo through all letters and get matching records with dictionary
for i in (2..total_number - 2)
first_array = keys[0..i]
next if first_array.length < 3
second_array = keys[i + 1..total_number]
next if second_array.length < 3
first_combination = first_array.shift.product(*first_array).map(&:join) # Get product of arrays #get_combination(first_array, dictionary)#
next if first_combination.nil?
second_combination = second_array.shift.product(*second_array).map(&:join)
next if second_combination.nil?
results[i] = [(first_combination & dictionary[i+2]), (second_combination & dictionary[total_number - i +1])] # get common values from arrays
end
#arrange words like we need as a output
final_words = []
results.each do |key, combinataions|
next if combinataions.first.nil? || combinataions.last.nil?
combinataions.first.product(combinataions.last).each do |combo_words|
final_words << combo_words
end
end
# for all numbers
final_words << (keys.shift.product(*keys).map(&:join) & dictionary[11]).join(", ") # matche with all character
time_end = Time.now()
puts "Time #{time_end.to_f - time_start.to_f}"
final_words
end

end

final_words = NumberToWordOpt.new().letter_combinations("6686787825")
print final_words
`