Decode WaysMedium

Decode Ways

Medium 12.3k35% acceptance

StringDynamic Programming

A message of letters is encoded to digits with the mapping A → "1", B → "2", …, Z → "26".

Given a string s of digits, return the number of ways to decode it back into letters.

A single digit "1"–"9" maps to one letter, and a pair "10"–"26" maps to one letter. Crucially, a leading zero is invalid: "0" alone has no letter, and pairs like "06" are not allowed. If the string cannot be decoded at all, return 0. The input is non-empty.

Example 1

Input: s = "12"

Output: 2

"12" decodes as "AB" (1, 2) or "L" (12) — two ways.

Example 2

Input: s = "226"

Output: 3

"BZ" (2 26), "VF" (22 6), or "BBF" (2 2 6).

Example 3

Input: s = "06"

Output: 0

A leading zero is invalid: "6" cannot be reached because "0" has no mapping and "06" is not a valid pair.

Constraints

1 ≤ s.length ≤ 100
s contains only digit characters 0–9.

Asked atMetaAmazonGoogleMicrosoft

JavaScript

⌘↵ to run

Loading editor…

Case 1

"12"

expected: 2

Case 2

"226"

expected: 3

Case 3

"06"

expected: 0

Case 4

"0"

expected: 0

Case 5

"10"

expected: 1

Case 6

"2101"

expected: 1

Case 7

"111111"

expected: 13