LeetCode Entry

91. Decode Ways

25.12.2023 medium 2023 kotlin

Ways to decode back 'A' -> '1', 'B' -> '2' … 'Z' -> '26'

91. Decode Ways medium blog post substack youtube image.png

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 successfull 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