221. Letter Combinations of a Phone Number (Count)

Given a string of digits 2-9, return the number of possible letter combinations the number could represent on a phone keypad (2-6,8 map to 3 letters; 7,9 map to 4). Return 0 for an empty string.

Input: A quoted digit string.

Output: Integer — number of combinations.

Examples

Input: "23"
Output: 9
Explanation: 3*3=9 combinations.

Input: ""
Output: 0
Explanation: Empty input.

Input: "79"
Output: 16
Explanation: 4*4=16.

Constraints

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

Asked by