25.12.2023
91. Decode Ways medium
blog post
youtube
Join me on Telegram
https://t.me/leetcode_daily_unstoppable/450
Problem TLDR
Ways to decode back ‘A’ -> ‘1’, ‘B’ -> ‘2’ … ‘Z’ -> ‘26’
Intuition
Let’s consider each position and do a DFS to check how many successful paths exist.
For each position, we know the answer for the rest of the string, so it can be cached.
Approach
Start from implementing brute-force DFS, consider two cases: take just one char and take two chars. After that, introduce the cache, it can be an array or a HashMap<position, result>. Extra step, is to notice, the current value only depends on the two next values, so rewrite DFS into a reversed loop and store two previous results. The boss step is to do some code golf.
Complexity
Time complexity:
O(n)Space complexity:
O(1)
Code
fun numDecodings(s: String): Int =
s.indices.reversed().fold(0 to 1) { (prev, curr), i ->
curr to if (s[i] == '0') 0 else
curr + if (s.drop(i).take(2).toInt() in 10..26) prev else 0
}.second