Funcia
Lv.2dpstring

Decode Ways

Memory limit
256 MB
Correctness time limit
10000 ms
Solvers
0
0

Letters are encoded A → 1 … Z → 26 and concatenated into the digit string s. Return the number of ways to decode s, modulo 1,000,000,0071{,}000{,}000{,}007. A lone "0" or a two-digit piece starting with 0 cannot be decoded.

Examples

sresult
"12"2
"226"3
"06"0
"2101"1

Efficiency

This problem has performance tests. Judge the required time complexity from the input sizes in the constraints.

Function signature

solution(s: string) → int

Constraints

  • 1≤1 \le s.length ≤100,000\le 100{,}000, digits only

Expected complexity

Time
O(N)
Space
O(1)

Examples

sExpected
"12"2
"226"3
"06"0
"2101"1

Hint

Hint

ways[i] = (s[i-1] != '0' ? ways[i-1] : 0) + (10 <= s[i-2..i) <= 26 ? ways[i-2] : 0), ways[0] = 1, all modulo the prime. Trying both readings recursively grows like Fibonacci on "111…1" and exceeds the time limit.

Time limits per language

LanguageEfficiency time limit
C (GCC, gnu17)200 msestimated
C++ (GCC, gnu++23)200 msderived
Python 3.131000 msderived
Java 251000 msderived
Kotlin 2.4 (JVM)1400 msestimated
C# 14 (.NET 10)1400 msestimated

Test groups

GroupWeightTestsVisibility
sample04inputs and outputs
correctness4010verdict only
performance604verdict only
Loading editor…
Log in to run or submit code.

No result yet. Run or submit your code.