Compute All Mnemonics For A Phone Number (Recursion/Backtracking Problem) @BackToBackSWE
Compute All Mnemonics For A Phone Number (Recursion/Backtracking Problem)  @BackToBackSWE
Uploaded December 2018 | Updated November 2026, 3 hours ago
Try Our Full Platform: nas.io/backtobackswe
πŸ“Ή Intuitive Video Explanations
❓New Unseen Questions
πŸ”Ž Get All Solutions


Question: Each digit, apart from 0 and 1, in a phone keypad corresponds to one of three or four letters of the alphabet. Write a program which takes asinput a phone number (specified as a string of digits) and returns all possible character sequences that correspond to the phone number.

3 Keys To Backtracking:

Our choice: At each number we can choose certain letters
Our constraints: none really
Our goal: Get a string as ling as the original number given

Time:

O(4^n) * O(1) * O(n) = O(n(4^n)) [weak upper bound]

Since there are no more than 4 possible characters for each digit, there will be O(4^n) function calls at max.

Each call of the function will make at max 4 more calls. 4 * 4 * 4 * 4 * 4... = 4^n, n being the amount of digits provided as input.

O(1) work in each function call for the most part

O(n) time to copy the string over to the answer list in each base case since that is done character by character.

Space:

O(n) + O(4^n) = O(4^n)

Our recursion tree will go at max n calls deep.

We will have at max 4 choices at each digits so total we have roughly 3^n or 4^n total mneumonics that pan out and get stored in the result array.

One could get more mathematically rigorous but that approximation is enough for an interview situation.

++++++++++++++++++++++++++++++++++++++++++++++++++

HackerRank: youtube.com/channel/UCOf7UPMHBjAavgD0Qw5q5ww

Tuschar Roy: youtube.com/user/tusharroy2525

GeeksForGeeks: youtube.com/channel/UC0RhatS1pyxInC00YKjjBqQ

Jarvis Johnson: youtube.com/user/VSympathyV

Success In Tech: youtube.com/channel/UC-vYrOAmtrx9sBzJAf3x_xw

++++++++++++++++++++++++++++++++++++++++++++++++++

This question is 7.7 in Elements of Programming Interviews.
Compute All Mnemonics For A Phone Number (Recursion/Backtracking Problem)Why Is Merge Sort O(n * log(n))? The Really Really Long Answer.Minimum Window Substring: Utilizing Two Pointers & Tracking Character Mappings With A HashtableWhat are Greedy Algorithms?An In-Depth Algorithmic Analysis of Bubble Sort. Best Case, Average Case, & Worst Case.Find The Longest Increasing Subsequence - Dynamic Programming FundamentalsImplement A Binary Heap - An Efficient Implementation of The Priority Queue ADT (Abstract Data Type)Coding Interview | Binary Tree Traversal #shorts #datastructures #binarytree #codinginterviewBinary Tree Level Order Traversal - Drawing The Parallel Between Trees & GraphsFind the kth Largest or Smallest Element of an Array: From Sorting To Heaps To PartitioningInterval Scheduling Maximization (Proof w/ Exchange Argument)Coding Interview Concept | Asymptotic Behaviour #shorts #datastructures #codinginterview
Back To Back SWE |

Compute All Mnemonics For A Phone Number (Recursion/Backtracking Problem)

SHARE TO X SHARE TO REDDIT SHARE TO FACEBOOK WALLPAPER