1. Letter Combinations of a Phone Number:
Problem: Given a string of digits like "23", return all the possible letter combinations that the number could represent on a telephone keypad.
Solution Steps
Use a dictionary to map digits to letters like the following: {'2': 'abc', '3': 'def',.
Now use backtracking in order to make a combination.
Start by an empty combination.
Append every letter that corresponds to each one of the digits in sequence
Try all possible combinations and go on until the input sequence is processed.
Example
Input: "23"
Output: ["ad", "ae", "af", "bd", "be", "bf", "cd", "ce", "cf"]
2. Generate Parentheses:
Problem: Generate all combinations of valid parentheses for n pairs.
Steps to Solve:
(Use backtracking):
Start with an empty string.
Keep track of the number of open '(' and close ')' brackets used.
Add '(' only if it will not exceed n.
Put ')' only if it wouldn't exceed the count of '(' already placed.
Input: n = 3
Output: [((())), (()()), (())(), ()()()]
Top comments (0)