Phone number to words based on the dictionary

Question

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

Answer 1

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)

Answer 2

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