[Leetcode 17] Letter Combinations of a Phone Number: https://leetcode.com/problems/letter-combinations-of-a-phone-number/

phone_letter_number_permutations.rb

# Given a phone number that contains digits from 2–9, find all possible letter 
# combinations the phone number could translate to.
#
# Example
# Input: "56"
# Output:["jm","jn","jo","km","kn","ko","lm","ln","lo"]
#
# Approach explanation
# All possible combinations: backtracking
# input.size * number of letters => 5,6 => 3*3 => 9
#
# State tree
#        j            k             l
#  m     n    o  m    n    o    m    n    o
#
# Algorithm:
# Base case: state.size == input.size
#
# Recursive case
# In order to fetch the letters we use the current state.size to determine the position of the digit
# we need to consider.
#
# For each letter of the given digit selected we:
#  - Add the current letter to the state
#  - Call the recursive function again
#  - Remove the current letter from the state
# 

# Code
KEYBOARD = {
  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'],
}.freeze

def dfs(input, state, result)
  if state.size == input.size
    result << state.join("")
    return
  end

  next_digit = input[state.size].to_i
  KEYBOARD[next_digit].each do |letter|
    state << letter
    dfs(input, state, result)
    state.pop
  end
end

def letter_combinations(digits)
  return [] if digits.size.zero?
  result = []
  state = []
  dfs(digits, state, result)
  result
end

# Test
input = "56"
result = letter_combinations(input)
puts result.join(", ")
puts result == ["jm","jn","jo","km","kn","ko","lm","ln","lo"]