Problem Statement

Given a message encoded using the following mapping:

'A' -> 1
'B' -> 1
...
'Z' -> 26

Implement a function that takes a string of digits and returns the number of ways it can be decoded back into its original message.

For example:

• Given the input '12', the possible decodings are 'AB' and 'L', so the output should be 2.
• For the input '226', the possible decodings are 'BZ', 'VF', and 'BBF', making the output 3.
• With the input '0', there are no valid decodings, resulting in an output of 0.

Implementation

Dynamic Programming

The DP solution is based on the bottom-up approach: first solve smaller problems, then combines results. No recursion overhead, O(n) time and space. See dp.go for implementation details.

Recursive Solutions

For the recursive solution, at each index, decide whether to decode 1 or 2 characters, then recursively solve the rest. This solution is further optimized using memoization, which caches results to avoid recomputing same subproblems.

The recursive_atoi.go implements recursive algorithm using strconv.Atoi() to convert substring to integer instead of manual digit arithmetic. More readable but slightly slower due to string parsing overhead. Use of digit arithmetic (as in recursive.go) optimizes the solution.

Benchmarks

Benchmarks compare all three solutions. Run:

go run *.go

Results show that dynamic programming approach is the most performant in both time and space complexity:

Testing with input: 1111111111111111111111 (100000 iterations)

DP                        Result: 28657, Time: 21.141791ms, Memory:    18750 KB
Recursive + Atoi          Result: 28657, Time: 83.139042ms, Memory:    91417 KB
Recursive + Arithmetic    Result: 28657, Time: 69.182292ms, Memory:    91406 KB