LeetCode 91. Decode Ways

October 16, 2020

We can use a greedy recursive algorithm that tries every possible next step. It keeps a count of paths that result in a fully decoded string.

We'll also use a cache to reduce our runtime to $O(n)$ .

from typing import Dict
import unittest

class Test(unittest.TestCase):

    def setUp(self):
        self.s = Solution()

    def test_examples(self):
        self.assertEqual(self.s.numDecodings("12"), 2)
        self.assertEqual(self.s.numDecodings("226"), 3)
        self.assertEqual(self.s.numDecodings("0"), 0)
        self.assertEqual(self.s.numDecodings("111111111111111111111111111111111111111111111"), 1836311903)

    def test_invalid(self):
        self.assertEqual(self.s.numDecodings("100"), 0)
        self.assertEqual(self.s.numDecodings("260"), 0)
        self.assertEqual(self.s.numDecodings("01"), 0)
        
    def test_long(self):
        self.assertEqual(self.s.numDecodings("18310261"), 4)



class Solution:

    def _helper(self, s: str, i: int, chrs: set, cache: Dict[int, int]) -> int:
        if i >= len(s):
            return 1
        if i in cache:
            return cache[i]
        cache[i] = 0
        one = s[i]
        if one in chrs:
            cache[i] += self._helper(s, i+1, chrs, cache)
        if len(s) - i < 2:
            return cache[i]
        two = s[i:i+2]
        if two in chrs:
            cache[i] += self._helper(s, i+2, chrs, cache)
        return cache[i]

    def numDecodings(self, s: str) -> int:
        chrs = {str(i) for i in range(1,27,1)}
        return self._helper(s, 0, chrs, {})

if __name__ == "__main__":
    unittest.main()