Letter Combinations of a Phone Number

medium

Acceptance: 48%

BacktrackingStrings

Each digit from 2 to 9 on a telephone keypad maps to a set of letters. Given a string of such digits, return every possible letter combination the digits could produce. The output may appear in any order.

Examples

Example 1:

Input:digits = "45"

Output:["gj","gk","gl","hj","hk","hl","ij","ik","il"]

Example 2:

Input:digits = "7"

Output:["p","q","r","s"]

Hints

import java.util.*;

class Solution {
    private static final String[] MAPPING = {"", "", "abc", "def", "ghi", "jkl", "mno", "pqrs", "tuv", "wxyz"};

    public List<String> letterCombinations(String digits) {
        List<String> result = new ArrayList<>();
        if (digits.isEmpty()) return result;
        backtrack(digits, 0, new StringBuilder(), result);
        return result;
    }

    private void backtrack(String digits, int idx, StringBuilder current, List<String> result) {
        if (idx == digits.length()) { result.add(current.toString()); return; }
        for (char c : MAPPING[digits.charAt(idx) - '0'].toCharArray()) {
            current.append(c);
            backtrack(digits, idx + 1, current, result);
            current.deleteCharAt(current.length() - 1);
        }
    }
}

Time complexityO(4^n)

Space complexityO(n)

Letter Combinations of a Phone Number

Examples

Hints

Related Problems