5
\$\begingroup\$

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
\$\endgroup\$
5
  • \$\begingroup\$ Where can we find the dictionary file, if we want to try this out? \$\endgroup\$
    – Flambino
    Mar 21 '17 at 12:11
  • \$\begingroup\$ @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 \$\endgroup\$
    – Thorin
    Mar 22 '17 at 4:46
  • 1
    \$\begingroup\$ this is the file: github.com/ansarmirza/assignment/blob/master/db/dictionary.txt \$\endgroup\$
    – Thorin
    Mar 22 '17 at 4:48
  • \$\begingroup\$ 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. \$\endgroup\$
    – user95591
    Mar 30 '17 at 14:56
  • \$\begingroup\$ Sorry that was edit by mistake, I have added the same thing again \$\endgroup\$
    – Thorin
    Mar 30 '17 at 14:57
4
\$\begingroup\$

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)

\$\endgroup\$
2
  • \$\begingroup\$ Yes dictionary is sorted \$\endgroup\$
    – Thorin
    Mar 22 '17 at 4:42
  • \$\begingroup\$ 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. \$\endgroup\$ Mar 22 '17 at 16:03
1
\$\begingroup\$

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
\$\endgroup\$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.