Letter Combinations
Given a string
s containing digits from 2 to 9 inclusive, write a program to return all possible letter combinations that the number could represent according to the mapping of digits to letters on a telephone keypad (image below). The letter combinations should be printed in lexicographical order.
Input
The input consists of a single line containing the string
s (1 ≤ |s| ≤ 10), where |s| represents the length of the string. The string s consists of digits from 2 to 9 inclusive.Output
Output all possible letter combinations that can be formed by the given
s, with each combination printed on a separate line. The letter combinations should be printed in lexicographical order.Examples
Input | Output |
25 | aj
ak
al
bj
bk
bl
cj
ck
cl |
Constraints
Time limit: 2 seconds
Memory limit: 512 MB
Output limit: 7 MB