752. Letter Combinations of a Phone Number

Given a string digits containing only characters from '2' through '9', return all possible letter combinations that could be produced on a telephone keypad, in lexicographic order. The keypad mapping is:
2 -> abc, 3 -> def, 4 -> ghi, 5 -> jkl, 6 -> mno, 7 -> pqrs, 8 -> tuv, 9 -> wxyz.
If digits is empty, return an empty list.

Input: A string digits consisting of characters '2'..'9' (or empty).

Output: Return a lexicographically sorted list of strings.

Examples

Input: "23"
Output: ["ad","ae","af","bd","be","bf","cd","ce","cf"]
Explanation: 3 x 3 = 9 combinations in lex order.

Input: ""
Output: []
Explanation: Empty input -> empty list.

Input: "2"
Output: ["a","b","c"]
Explanation: Letters for digit 2.

Constraints

• 0 <= digits.length <= 4
• digits[i] in '2'..'9'

Asked by