Skip to main content

Leetcode 17: Letter Combinations of a Phone Number

 

1. Problem Statement (Simple Explanation):


You’re given a string digits consisting of characters '2'–'9'.

Each digit maps to some letters like on a classic phone keypad:

  • 2 → "abc"

  • 3 → "def"

  • 4 → "ghi"

  • 5 → "jkl"

  • 6 → "mno"

  • 7 → "pqrs"

  • 8 → "tuv"

  • 9 → "wxyz"

You need to return all possible letter combinations that the input number could represent.

  • Order of combinations does not matter.

  • If digits is empty, the answer is an empty list (LeetCode variant usually states that; here constraints start from length 1).


2. Examples:


Example 1:

Input: digits = "23"

Digit-to-letters:

  • 2 → ["a","b","c"]

  • 3 → ["d","e","f"]

All combinations (cartesian product):

  • "a" + "d" = "ad"

  • "a" + "e" = "ae"

  • "a" + "f" = "af"

  • "b" + "d" = "bd"

  • "b" + "e" = "be"

  • "b" + "f" = "bf"

  • "c" + "d" = "cd"

  • "c" + "e" = "ce"

  • "c" + "f" = "cf"

Output: ["ad","ae","af","bd","be","bf","cd","ce","cf"]


Example 2:

Input: digits = "2"

Output: ["a","b","c"]

Constraints:

  • 1<=digits.length<=41

  • digits[i] is in '2'–'9'


3. Approach – Backtracking / DFS (Standard):


This is a classic backtracking (depth-first search) problem.


Intuition:

We build combinations digit by digit:

  • At position i in digits, we choose one letter from the mapping of digits[i], append it to the current path, and recurse to fill the next position.

  • When our current combination length equals len(digits), we have a complete combination; add it to the result.

Since digits.length <= 4 and each digit maps to at most 4 letters (7/9 → 4 letters), the total combinations are at most:

44-256

Very small, so recursive backtracking is perfect.


Algorithm (Step-by-Step):

  1. If digits is empty, return empty list.

  2. Create a mapping from digit char to its string of letters:

    • '2' → "abc", '3' → "def", ..., '9' → "wxyz".

  3. Create an empty list result to store combinations.

  4. Define a recursive function backtrack(index, currentCombination):

    • If index == len(digits):

      • We formed a full combination → add currentCombination to result, return.

    • Else:

      • Let digit = digits[index].

      • Let letters = mapping[digit].

      • For each letter in letters:

        • Append letter to currentCombination.

        • Call backtrack(index + 1, currentCombination).

        • Remove letter (backtrack) if using a mutable builder.

  5. Call backtrack(0, "").

  6. Return result.


Pseudo-code:



Complexity:

Let:

  • n = len(digits) (max 4)

  • Each digit maps to up to 4 letters.

Number of combinations: at most 4n.

  • Time: O(4n)

  • Space:

    • Recursion depth at most n.

    • Result list stores all combinations. So asymptotic auxiliary space is O(n) (excluding output).


4. Java code:



5. C code:



6. C++ code:



7. Python code:



8. JavaScript code:




Comments

Post a Comment

Popular posts from this blog

Leetcode 1: Two Sum

  Leetcode Link: https://leetcode.com/problems/two-sum/ 1. Problem Statement (Simple Explanation) You are given: An array of integers nums An integer target You need to  return the indices of two numbers in the array  such that: Conditions: Each input has  exactly one solution . You  cannot use the same element twice . You can return the answer in  any order . 2. Examples Example 1 Input:                                    nums = [2, 7, 11, 15], target = 9 Output:                                 [0, 1] Explanation:                     nums[0]+nums[1]=2+7=9              So we return [0, 1]. Example 2 Input:           ...
Post a Comment
Read more

Leetcode 3: Longest Substring Without Repeating Characters

  Leetcode Link 1. Problem Statement (Simple Explanation) You are given a string s. You need to find the length of the longest substring of s that does not  contain any repeated characters. A substring is a contiguous sequence of characters in the string. You must return an integer length, not the substring itself. 2. Examples Example 1 Input: s = "abcabcbb" Output: 3 Explanation: Some substrings without repeating characters: "abc", "bca", "cab"The longest length is 3. Example 2 Input: s = "bbbbb" Output: 1 Explanation: All substrings that are valid are just "b". The longest length is 1. Example 3 Input:   s = "pwwkew" Output:   3 Explanation: Possible substrings without repetition: "pw", "wke", "kew". "wke" or "kew" have length 3. "pwke" is not valid because it’s not contiguous in the original string (p and k are separated by ww). Constraints...
Post a Comment
Read more

Leetcode 2: Add Two Numbers

Leetcode Link: https://leetcode.com/problems/add-two-numbers/ 1. Problem Statement (Simple Explanation) You are given  two non-empty linked lists , l1 and l2, that represent two non-negative integers. Each node contains a  single digit . The digits are stored in  reverse order  (i.e., the 1’s digit is at the head). You need to  add the two numbers  and return the  sum as a linked list , also in reverse order. You can assume: There are  no leading zeros , except when the number itself is 0. 2. Examples Example 1 Input:                l1 = [2,4,3]                l2 = [5,6,4]           Interpreting linked lists as numbers (reverse order): l1 represents 342 l2 represents 465 Output:                [7,0,8] Explanation:        ...
Post a Comment
Read more