decode_ways

View Source

 1from functools import cache
 2
 3
 4# @leet start
 5class Solution:
 6    def numDecodings(self, s: str) -> int:
 7        """
 8        This question gives us a decoding that isn't a prefix decoding, so
 9        sometimes the prefixes can overlap. Since we're encoding lowercase
10        english letters, the message comes in 1-26, and since its a stream,
11        we can decode each pair of letters more than one way if it falls in
12        between 1 - 26.
13
14        Also note that a leading '0' in a string is invalid, so if we chooose
15        '11106' and pick '11', '1', '06', it is invalid. We would return 0
16        in this case.
17
18        So, for this question, we have a few conditions:
19        1. If we've hit the end of the string, we return 1 for success.
20        2. If our current character is a 0, return 0 for invalid decoding.
21
22        Otherwise, we check the next two letters in the stream. If they decode
23        to 1 - 26, we return the count of the decodings of if we took the next
24        letter and the next two letters.
25
26        Otherwise, we can just advance our pointer once.
27        """
28
29        @cache
30        def dp(index, s):
31            if index == len(s):
32                return 1
33            if s[index] == "0":
34                return 0
35            if index == len(s) - 1:
36                return 1
37
38            if int(s[index : index + 2]) <= 26:
39                return dp(index + 1, s) + dp(index + 2, s)
40            return dp(index + 1, s)
41
42        return dp(0, s)
43
44
45# @leet end
46
47
48def test():
49    assert 2 + 2 == 4

class Solution: View Source

 6class Solution:
 7    def numDecodings(self, s: str) -> int:
 8        """
 9        This question gives us a decoding that isn't a prefix decoding, so
10        sometimes the prefixes can overlap. Since we're encoding lowercase
11        english letters, the message comes in 1-26, and since its a stream,
12        we can decode each pair of letters more than one way if it falls in
13        between 1 - 26.
14
15        Also note that a leading '0' in a string is invalid, so if we chooose
16        '11106' and pick '11', '1', '06', it is invalid. We would return 0
17        in this case.
18
19        So, for this question, we have a few conditions:
20        1. If we've hit the end of the string, we return 1 for success.
21        2. If our current character is a 0, return 0 for invalid decoding.
22
23        Otherwise, we check the next two letters in the stream. If they decode
24        to 1 - 26, we return the count of the decodings of if we took the next
25        letter and the next two letters.
26
27        Otherwise, we can just advance our pointer once.
28        """
29
30        @cache
31        def dp(index, s):
32            if index == len(s):
33                return 1
34            if s[index] == "0":
35                return 0
36            if index == len(s) - 1:
37                return 1
38
39            if int(s[index : index + 2]) <= 26:
40                return dp(index + 1, s) + dp(index + 2, s)
41            return dp(index + 1, s)
42
43        return dp(0, s)

def numDecodings(self, s: str) -> int: View Source

 7    def numDecodings(self, s: str) -> int:
 8        """
 9        This question gives us a decoding that isn't a prefix decoding, so
10        sometimes the prefixes can overlap. Since we're encoding lowercase
11        english letters, the message comes in 1-26, and since its a stream,
12        we can decode each pair of letters more than one way if it falls in
13        between 1 - 26.
14
15        Also note that a leading '0' in a string is invalid, so if we chooose
16        '11106' and pick '11', '1', '06', it is invalid. We would return 0
17        in this case.
18
19        So, for this question, we have a few conditions:
20        1. If we've hit the end of the string, we return 1 for success.
21        2. If our current character is a 0, return 0 for invalid decoding.
22
23        Otherwise, we check the next two letters in the stream. If they decode
24        to 1 - 26, we return the count of the decodings of if we took the next
25        letter and the next two letters.
26
27        Otherwise, we can just advance our pointer once.
28        """
29
30        @cache
31        def dp(index, s):
32            if index == len(s):
33                return 1
34            if s[index] == "0":
35                return 0
36            if index == len(s) - 1:
37                return 1
38
39            if int(s[index : index + 2]) <= 26:
40                return dp(index + 1, s) + dp(index + 2, s)
41            return dp(index + 1, s)
42
43        return dp(0, s)

This question gives us a decoding that isn't a prefix decoding, so sometimes the prefixes can overlap. Since we're encoding lowercase english letters, the message comes in 1-26, and since its a stream, we can decode each pair of letters more than one way if it falls in between 1 - 26.

Also note that a leading '0' in a string is invalid, so if we chooose '11106' and pick '11', '1', '06', it is invalid. We would return 0 in this case.

So, for this question, we have a few conditions:

If we've hit the end of the string, we return 1 for success.
If our current character is a 0, return 0 for invalid decoding.

Otherwise, we check the next two letters in the stream. If they decode to 1 - 26, we return the count of the decodings of if we took the next letter and the next two letters.

Otherwise, we can just advance our pointer once.

def test(): View Source

49def test():
50    assert 2 + 2 == 4