Decode Ways II

Problem

A message containing letters from A-Z can be encoded into numbers using the following mapping:

1
2
3
4


'A' -> "1"
'B' -> "2"
...
'Z' -> "26"

To decode an encoded message, all the digits must be grouped then mapped back into letters using the reverse of the mapping above (there may be multiple ways). For example, "11106" can be mapped into:

"AAJF" with the grouping (1 1 10 6)
"KJF" with the grouping (11 10 6)

Note that the grouping (1 11 06) is invalid because "06" cannot be mapped into 'F' since "6" is different from "06".

In addition to the mapping above, an encoded message may contain the '*' character, which can represent any digit from '1' to '9' ('0' is excluded). For example, the encoded message "1*" may represent any of the encoded messages "11", "12", "13", "14", "15", "16", "17", "18", or "19". Decoding "1*" is equivalent to decoding any of the encoded messages it can represent.

Given a string s consisting of digits and '*' characters, return the number of ways to decode it.

Since the answer may be very large, return it modulo 10^9 + 7.

Examples

Example 1:

1
2
3
4
5


Input: s = "*"
Output: 9
Explanation: The encoded message can represent any of the encoded messages "1", "2", "3", "4", "5", "6", "7", "8", or "9".
Each of these can be decoded to the strings "A", "B", "C", "D", "E", "F", "G", "H", and "I" respectively.
Hence, there are a total of 9 ways to decode "*".

Example 2:

1
2
3
4
5


Input: s = "1*"
Output: 18
Explanation: The encoded message can represent any of the encoded messages "11", "12", "13", "14", "15", "16", "17", "18", or "19".
Each of these encoded messages have 2 ways to be decoded (e.g. "11" can be decoded to "AA" or "K").
Hence, there are a total of 9 * 2 = 18 ways to decode "1*".

Example 3:

1
2
3
4
5


Input: s = "2*"
Output: 15
Explanation: The encoded message can represent any of the encoded messages "21", "22", "23", "24", "25", "26", "27", "28", or "29".
"21", "22", "23", "24", "25", and "26" have 2 ways of being decoded, but "27", "28", and "29" only have 1 way.
Hence, there are a total of (6 * 2) + (3 * 1) = 12 + 3 = 15 ways to decode "2*".

Solution

Method 1 – Dynamic Programming with State Compression

Intuition

The problem is an extension of the classic “Decode Ways” problem, but with the wildcard * that can represent digits 1-9. We use dynamic programming to count the number of ways to decode the string, considering both single and double character decodings at each step. The key is to handle the * character carefully for both single and double digit possibilities.

Approach

Initialize three variables: a (ways to decode up to i-2), b (ways to decode up to i-1), and ans (ways to decode up to i).
Iterate through the string:

For each character, calculate the number of ways to decode it as a single character.
Also, calculate the number of ways to decode it together with the previous character (as a pair).
Handle cases where either or both characters are *.

Update the DP variables for the next iteration.
Return the final answer modulo 10^9 + 7.

C++

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28


class Solution {
public:
   int numDecodings(string s) {
      int mod = 1e9 + 7, n = s.size();
      long a = 1, b = 1, ans = 0;
      for (int i = 0; i < n; ++i) {
        ans = 0;
        if (s[i] == '*') ans = (b * 9) % mod;
        else if (s[i] != '0') ans = b;
        if (i > 0) {
           if (s[i-1] == '*' && s[i] == '*') ans = (ans + a * 15) % mod;
           else if (s[i-1] == '*') {
              if (s[i] <= '6') ans = (ans + a * 2) % mod;
              else ans = (ans + a) % mod;
           } else if (s[i] == '*') {
              if (s[i-1] == '1') ans = (ans + a * 9) % mod;
              else if (s[i-1] == '2') ans = (ans + a * 6) % mod;
           } else {
              int num = (s[i-1] - '0') * 10 + (s[i] - '0');
              if (num >= 10 && num <= 26) ans = (ans + a) % mod;
           }
        }
        a = b;
        b = ans;
      }
      return ans;
   }
}

Go

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36


func numDecodings(s string) int {
   mod := int(1e9 + 7)
   a, b, ans := 1, 1, 0
   for i := 0; i < len(s); i++ {
      ans = 0
      if s[i] == '*' {
        ans = (b * 9) % mod
      } else if s[i] != '0' {
        ans = b
      }
      if i > 0 {
        if s[i-1] == '*' && s[i] == '*' {
           ans = (ans + a*15) % mod
        } else if s[i-1] == '*' {
           if s[i] <= '6' {
              ans = (ans + a*2) % mod
           } else {
              ans = (ans + a) % mod
           }
        } else if s[i] == '*' {
           if s[i-1] == '1' {
              ans = (ans + a*9) % mod
           } else if s[i-1] == '2' {
              ans = (ans + a*6) % mod
           }
        } else {
           num := (int(s[i-1]-'0'))*10 + int(s[i]-'0')
           if num >= 10 && num <= 26 {
              ans = (ans + a) % mod
           }
        }
      }
      a, b = b, ans
   }
   return ans
}

Java

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28


class Solution {
   public int numDecodings(String s) {
      int mod = 1000000007, n = s.length();
      long a = 1, b = 1, ans = 0;
      for (int i = 0; i < n; ++i) {
        ans = 0;
        if (s.charAt(i) == '*') ans = (b * 9) % mod;
        else if (s.charAt(i) != '0') ans = b;
        if (i > 0) {
           char p = s.charAt(i-1), c = s.charAt(i);
           if (p == '*' && c == '*') ans = (ans + a * 15) % mod;
           else if (p == '*') {
              if (c <= '6') ans = (ans + a * 2) % mod;
              else ans = (ans + a) % mod;
           } else if (c == '*') {
              if (p == '1') ans = (ans + a * 9) % mod;
              else if (p == '2') ans = (ans + a * 6) % mod;
           } else {
              int num = (p - '0') * 10 + (c - '0');
              if (num >= 10 && num <= 26) ans = (ans + a) % mod;
           }
        }
        a = b;
        b = ans;
      }
      return (int)ans;
   }
}

Kotlin

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31


class Solution {
   fun numDecodings(s: String): Int {
      val mod = 1_000_000_007
      var a = 1L
      var b = 1L
      var ans = 0L
      for (i in s.indices) {
        ans = 0L
        if (s[i] == '*') ans = (b * 9) % mod
        else if (s[i] != '0') ans = b
        if (i > 0) {
           val p = s[i-1]
           val c = s[i]
           if (p == '*' && c == '*') ans = (ans + a * 15) % mod
           else if (p == '*') {
              if (c <= '6') ans = (ans + a * 2) % mod
              else ans = (ans + a) % mod
           } else if (c == '*') {
              if (p == '1') ans = (ans + a * 9) % mod
              else if (p == '2') ans = (ans + a * 6) % mod
           } else {
              val num = (p - '0') * 10 + (c - '0')
              if (num in 10..26) ans = (ans + a) % mod
           }
        }
        a = b
        b = ans
      }
      return ans.toInt()
   }
}

Python

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32


class Solution:
   def numDecodings(self, s: str) -> int:
      mod: int = 10**9 + 7
      a: int = 1
      b: int = 1
      ans: int = 0
      for i, ch in enumerate(s):
        ans = 0
        if ch == '*':
           ans = (b * 9) % mod
        elif ch != '0':
           ans = b
        if i > 0:
           p = s[i-1]
           if p == '*' and ch == '*':
              ans = (ans + a * 15) % mod
           elif p == '*':
              if ch <= '6':
                ans = (ans + a * 2) % mod
              else:
                ans = (ans + a) % mod
           elif ch == '*':
              if p == '1':
                ans = (ans + a * 9) % mod
              elif p == '2':
                ans = (ans + a * 6) % mod
           else:
              num = int(p) * 10 + int(ch)
              if 10 <= num <= 26:
                ans = (ans + a) % mod
        a, b = b, ans
      return ans

Rust

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42


impl Solution {
   pub fn num_decodings(s: String) -> i32 {
      let m = 1_000_000_007;
      let (mut a, mut b, mut ans) = (1i64, 1i64, 0i64);
      let s = s.as_bytes();
      for i in 0..s.len() {
        ans = 0;
        if s[i] == b'*' {
           ans = (b * 9) % m;
        } else if s[i] != b'0' {
           ans = b;
        }
        if i > 0 {
           let p = s[i-1];
           let c = s[i];
           if p == b'*' && c == b'*' {
              ans = (ans + a * 15) % m;
           } else if p == b'*' {
              if c <= b'6' {
                ans = (ans + a * 2) % m;
              } else {
                ans = (ans + a) % m;
              }
           } else if c == b'*' {
              if p == b'1' {
                ans = (ans + a * 9) % m;
              } else if p == b'2' {
                ans = (ans + a * 6) % m;
              }
           } else {
              let num = (p - b'0') as i32 * 10 + (c - b'0') as i32;
              if num >= 10 && num <= 26 {
                ans = (ans + a) % m;
              }
           }
        }
        a = b;
        b = ans;
      }
      ans as i32
   }
}

Complexity

Time: O(n) where n is the length of the string.
Space: O(1) (constant extra space, only a few variables used).

Problem#

Examples#

Similar Problems#

Solution#

Method 1 – Dynamic Programming with State Compression#

Intuition#

Approach#

C++#

Go#

Java#

Kotlin#

Python#

Rust#

Complexity#