Each phone digit from 2 to 9 maps to a few letters. Return all letter strings that the digits could represent.
DSA Animator › DSA Revision › Backtracking › Letter Combinations of a Phone Number
Remember: one tree level per digit. The branching factor is the number of letters. The video solves Letter Combinations of a Phone Number (LeetCode 17, Medium) with the Backtracking on Digits pattern from the Backtracking topic, and you can replay every step in the interactive Letter Combinations of a Phone Number animation.
Each phone digit from 2 to 9 maps to a few letters. Return all letter strings that the digits could represent.
For 2 3, the digit 2 gives a b c and 3 gives d e f. So the answer is 9 strings, from a d to c f.
Nested loops only work when you know the number of digits. Recursion handles any length.
Each level of the tree is one digit. At a level, try every letter of that digit, append it, and recurse. When the string is as long as the digits, record it.
Pick a for the digit 2. For the digit 3, append d, e and f, recording a d, a e and a f. Backtrack and pick b, recording b d, b e and b f. Then c gives c d, c e and c f. That makes all 9 combinations.
In code, a map holds the letters of each digit. If the index equals the number of digits, record the string. Otherwise loop over the letters of the current digit, append, recurse, and remove. It's O of 4 to the n times n, since some digits have 4 letters.
Remember: one tree level per digit. The branching factor is the number of letters.