90. Decode Ways

Why this works

To decode a string, we can try taking 1 digit (if valid, i.e., not '0') or 2 digits (if valid, between 10 and 26).

The subproblem `dfs(i)` returns the number of valid decodings starting at index `i`.

Without memoization, the call tree has overlapping subproblems that lead to exponential O(2^N) time.

By storing computed subproblem states in a memo map, we ensure each index is solved at most once, reducing time complexity to O(N).