Practice/Meta/Leetcode 91. Decode Ways

Leetcode 91. Decode Ways

CodingOptional

Problem

You are building a message decoder that converts numeric strings into letters. Each letter is represented by a number: 'A' = 1, 'B' = 2, 'C' = 3, ..., 'Z' = 26.

Given a string containing only digits, determine how many different ways the string can be decoded into a valid sequence of letters.

Important decoding rules:

• Each code must be between 1 and 26 (inclusive)
• Single digit codes are: 1, 2, 3, ..., 9 (not 0)
• Two-digit codes are: 10, 11, 12, ..., 26 (cannot start with 0, cannot exceed 26)

If the string cannot be decoded (contains invalid patterns), return 0.

Requirements

1. Count all possible ways to partition the input string into valid letter codes
2. Handle strings containing '0' correctly (0 is only valid when paired with 1 or 2 to form 10 or 20)
3. Reject invalid patterns like standalone '0', '00', or two-digit numbers starting with '0' (except 10, 20)
4. Return 0 if no valid decoding exists
5. Return the total count of distinct valid decodings

Constraints

• 1 ≤ s.length ≤ 100
• s contains only digits
• Expected time complexity: O(n) where n is the length of the string
• Expected space complexity: O(1) with optimized DP or O(n) with memoization

Examples

Example 1:

` Input: s = "12" Output: 2 Explanation: This can be decoded as:

• "1" + "2" → "AB"
• "12" → "L" Total: 2 ways `

Example 2:

` Input: s = "226" Output: 3 Explanation: This can be decoded as:

• "2" + "2" + "6" → "BBF"
• "22" + "6" → "VF"
• "2" + "26" → "BZ" Total: 3 ways `

Example 3:

Input: s = "06" Output: 0 Explanation: "0" is not a valid code. "06" is invalid because two-digit codes cannot start with '0'. No valid decoding exists.

Example 4:

Input: s = "10" Output: 1 Explanation: Only one way: "10" → "J"