algorithm_fridays_week08.py

num_alpha_map = {
  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'],
}
combination_list = []

def performCombinations(list_of_list):
  ''' Helper Function: Perform and store combinations of inner arrays

  Time Complexity: TC
  Space Complexity: SC

  This is the meat of the solution

  This takes O(N) for TC irrespective of the length of the *numbers*
  where N in this case is the total number of possible combinations, and NOT *numbers*,
  *numbers* being the initial value passsed in to *find_combination* function

  N as the total number of possible combinations, is the multiplication of
  the length of the alphabets withtin each distinct number in *numbers*

  Whilst we have multiple smaller loops inside the initial while loop,
  those mostly take O(1), becuase it's always constant per *numbers* given

  The initial while loop stores the combination on every iteration.
  Though the condition for the loop is always True, it stops after
  the last possible combination, ending the loop, causing TC of O(N)

  SC is also O(N), N being same as above, total number of possible combinations
  becuase we had to create an array to store all the possible combinations
  '''

  # Length of outer array
  length = len(list_of_list)

  # To maintain the index position per time of the inner arrays
  pos = [0] * length # Initial value per inner array is 0 to indicate first alphabet

  while True:
    current_combo = ''

    # Get current combination
    for i in range(length):
      current_combo += list_of_list[i][pos[i]]

    # Store current combination
    combination_list.append(current_combo)

    # Find index of the last inner array with UNCONSUMED elements.
    # Decrement this index if elements of the current last array
    # has been iterated through (CONSUMED) on current combination iteration
    # 
    current_last_array_index = length - 1 # Initial last array index is the length - 1
    while current_last_array_index >= 0 and (pos[current_last_array_index] + 1 >= len(list_of_list[current_last_array_index])):
      current_last_array_index -= 1

    # If the index of the CURRENT last array is the less than index of the first array
    # then we've reached the end, we've iterated through all possible combinations
    # We exit the top level while loop
    # 
    if current_last_array_index < 0:
      break

    # Increment index position of the CUURENT last array with
    # UNCONSUMED elements for the current combination iteration
    pos[current_last_array_index] += 1

    for i in range(current_last_array_index + 1, length):
      pos[i] = 0


def find_combination(numbers):
  '''Main Function'''

  if type(numbers) != int or numbers < 2: return []

  list_of_list =  []
  num_list = [int(i) for i in str(numbers)]

  for num in num_list:
    # Append the alphabets array of each distinct number to a higher array of arrays
    list_of_list.append(num_alpha_map[num])

  performCombinations(list_of_list)
  return combination_list

if __name__ == '__main__':
  numbers = 23
  combinations = find_combination(numbers)
  print(combinations)

Hello @toritsejuFO, congratulations 🎉 your solution has been selected as one of the winning solutions in Week 8 of #AlgorithmFridays.

Your solution is clean, readable and passed the tests. It's really nice to see an iterative approach to solving this problem. Really neat!

However, out of the many winning solutions, only 3 will be selected for the $20 prize in a raffle draw. The raffle draw will hold today, Friday June 4 at 3.00pm WAT (7.00 am PST)

If you are interested in being a part of the raffle draw, please send me a DM on Twitter @meekg33k so I can share the event invite with you.

NB: Only solutions of participants who indicated interest in the raffle draw will be considered.

Thanks once again for participating and see you later today for Week 9 of #AlgorithmFridays.

Thanks @meekg33k.