Phone number mnemonic

Write a function which takes as input a phone number, specified as a string of digits, return all possible character sequences that correspond to the phone number. The cell phone keypad is specified by a mapping M that takes a digit and returns the corresponding set of characters. The character sequences do not have to be legal words or phrases.

Example

PhoneMnemonic.new('23') #=> AD, AE, AF, BD, BE, BF ..

Algorithm

Use backtracking

• Start with the last phone number
• Append all its chars into an array
• Move to the next phone number and compute all combinations of the current number and all chars previously in the array
• Repeat this until we reach the first digit

Code

class PhoneMnemonic
  def initialize(phone_number)
    cell_phone_mapping = {
        '2' => 'ABC',
        '3' => 'DEF',
        '4' => 'GHI',
        '5' => 'JKL',
        '6' => 'MNO',
        '7' => 'PQRS',
        '8' => 'TUV',
        '9' => 'WXYZ',
        '0' => '',
        '1' => ''
    }

    puts generate_char_sequences(cell_phone_mapping, phone_number)
  end

  def generate_char_sequences(cell_phone_mapping, phone_number)
    result_array = initialize_result_array(cell_phone_mapping[phone_number[phone_number.size - 1]])

    i = phone_number.size - 2
    while (i >= 0)
      next_result_array = combine_char_with_result_array(cell_phone_mapping[phone_number[i]], result_array)
      result_array = next_result_array
      next_result_array = []
      i -= 1
    end

    result_array
  end

  # Initialize result set with all values from the last number
  def initialize_result_array(letters)
    result_array = []
    letters.each_char do |c|
      result_array << c
    end

    result_array
  end

  def combine_char_with_result_array(letters, result_array)
    next_result_array = []
    letters.each_char do |c|
      result_array.each do |r|
        next_result_array << c + r
      end
    end

    next_result_array
  end
end

Time complexity

Since there are no more than 4 possible characters for each digit, the number of recursive calls T(n) satisfies T(n) ≤ 4T(n − 1), which solves to T(n) = O(4^n). For the function calls that entail recursion, the time spent within the function, not including the recursive calls, is O(1). For the base case, printing a sequence of length n takes time O(n). Therefore, the time complexity is O(4^n * n).