Decode ways ii

String Dynamic Programming

31.7% acceptance

Feb 20, 2026

1653

825

Given a string s with digits and '*' characters, return the number of ways to decode it modulo 10^9 + 7.

Solution

Rust

Time O(n)

Space O(n)

LeetCode

solution.rs

impl Solution {
  pub fn num_decodings(s: String) -> i32 {
    const MOD: i64 = 1_000_000_007;
    let s = s.as_bytes();
    let n = s.len();
    let mut dp = vec![0i64; n + 1];
    dp[0] = 1;
    dp[1] = if s[0] == b'*' { 9 } else if s[0] != b'0' { 1 } else { 0 };
    for i in 2..=n {
      let c = s[i - 1];
      let p = s[i - 2];
      // Single character
      if c == b'*' {
        dp[i] = (dp[i] + 9 * dp[i - 1]) % MOD;
      } else if c != b'0' {
        dp[i] = (dp[i] + dp[i - 1]) % MOD;
      }
      // Two characters
      if p == b'*' {
        if c == b'*' {
          dp[i] = (dp[i] + 15 * dp[i - 2]) % MOD;
        } else if c <= b'6' {
          dp[i] = (dp[i] + 2 * dp[i - 2]) % MOD;
        } else {
          dp[i] = (dp[i] + dp[i - 2]) % MOD;
        }
      } else if p == b'1' {
        if c == b'*' {
          dp[i] = (dp[i] + 9 * dp[i - 2]) % MOD;
        } else {
          dp[i] = (dp[i] + dp[i - 2]) % MOD;
        }
      } else if p == b'2' {
        if c == b'*' {
          dp[i] = (dp[i] + 6 * dp[i - 2]) % MOD;
        } else if c <= b'6' {
          dp[i] = (dp[i] + dp[i - 2]) % MOD;
        }
      }
    }
    dp[n] as i32
  }
}