764. Decode Ways (Recursive + Memoization, Modulo 10^9+7)

A message containing letters from A-Z is encoded to digits using the mapping 'A' -> "1", 'B' -> "2", ..., 'Z' -> "26". Given a string s containing only digits, return the number of ways to decode it, taken modulo 10^9 + 7. Note: a decoding is invalid if it would start with '0' or consume a two-digit group outside 10..26. If s cannot be decoded at all (e.g., starts with '0' or contains an unavoidable '0'), return 0. Implement with recursion + memoization.

Input: A string s of digits (enclosed in double quotes).

Output: Return an integer equal to the decoding count mod (10^9 + 7).

Examples

Input: "12"
Output: 2
Explanation: "AB" (1 2) or "L" (12).

Input: "226"
Output: 3
Explanation: "BZ" (2 26), "VF" (22 6), "BBF" (2 2 6).

Input: "06"
Output: 0
Explanation: Leading 0 cannot be decoded.

Constraints

• 1 <= s.length <= 100
• s contains only digits 0..9

Asked by