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 = k

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

StackExchange Code Review Q#158367, answer score: 4