Letter Phone Combinations
Logical Breakdown
- [ ] Subproblem Identification:
- [ ] Optimal Substructure:
- [ ] Constraint Handling: (e.g., Modulo \(10^9 + 7\))
- [ ] Optimization: (Matrix Exponentiation if 'A' is huge)
Mathematical Rigor
State Definition
Let \(dp[i]\) be the state for the \(i\)-th subproblem.
Recurrence Relation
Visualization
Complexity Analysis
| Approach | Time Complexity | Space Complexity |
|---|---|---|
| Iterative DP | \(O(N)\) | \(O(1)\) |
Code Reference
package com.dsa.recursion;
import java.util.*;
/ * Problem: Letter Phone Combinations * Group: 07. Recursion */ / * ============================================================================================ * PROBLEM: Letter Phone * ============================================================================================ * * --------------------- * 1. Problem Description * --------------------- * Given a digit string A, return all possible letter combinations that the number could represent. * * Mapping (Standard Telephone Keypad): * 0 -> "0" * 1 -> "1" * 2 -> "abc" * 3 -> "def" * 4 -> "ghi" * 5 -> "jkl" * 6 -> "mno" * 7 -> "pqrs" * 8 -> "tuv" * 9 -> "wxyz" * * Constraints: * - The returned strings must be lexicographically sorted. * - Digits 0 and 1 map to themselves (unlike some variations where they map to spaces or nothing). * * --------------------- * 2. Logical Breakdown & Mathematical Formulation * --------------------- * Let M be the mapping array where M[d] is the string of characters for digit d. * Let F(index, currentString) be the recursive function. * * State Transition (Backtracking): * For a digit d = A[index]: * 1. Retrieve the possible characters chars = M[d]. * 2. For each character 'c' in 'chars': * - Append 'c' to 'currentString'. * - Recursively call F(index + 1, currentString + c). * - Backtrack (remove 'c') implicitly by passing a new string or using a StringBuilder. * * Recurrence Relation: * Result = Union of { c + S | for all c in M[A[index]], for all S in F(index + 1) } * * Base Case: * If index == length(A): * We have formed a complete valid combination. Add 'currentString' to the result list. * * --------------------- * 3. Constraints & Complexity Analysis * --------------------- * Constraints: * 1 <= |A| <= 10 * * Time Complexity: * O(4^N * N) * - In the worst case (e.g., digits 7 or 9), each digit branches into 4 possibilities. * - There are at most 4^N leaf nodes in the recursion tree. * - At each leaf, we construct a string of length N. * - For N=10, 4^10 approx 10^6, which fits easily within 1 second. * * Space Complexity: * O(N) - Recursion stack depth is equal to the length of the string A. * * --------------------- * 4. Input / Output Format * --------------------- * Input: String A (containing digits '0'-'9'). * Output: List of Strings representing all combinations. * * --------------------- * 5. Examples * --------------------- * Input 1: A = "23" * - '2' -> "abc". Branches: 'a', 'b', 'c' * - '3' -> "def". * - Path 'a': adds "ad", "ae", "af" * - Path 'b': adds "bd", "be", "bf" * - Path 'c': adds "cd", "ce", "cf" * Output 1: ["ad", "ae", "af", "bd", "be", "bf", "cd", "ce", "cf"] * * Input 2: A = "012" * - '0' -> "0". (Fixed) * - '1' -> "1". (Fixed) * - '2' -> "abc". * Output 2: ["01a", "01b", "01c"] * * ============================================================================================ */ public class LetterPhoneCombinations { public int solve(int A) { // TODO: Implement solution return 0; }
public ArrayList<String> letterCombinations(String input4) {
return new ArrayList<>();
}
}