Cuente la posible decodificación de una secuencia de dígitos dada con caracteres ocultos

Dada una string S que contiene dígitos y el carácter ‘*’, es decir, un carácter oculto, la tarea es encontrar el número de formas de decodificar este carácter oculto de la string dada.

Dado que la respuesta puede ser muy grande, devuélvela módulo 10 9 +7.

Una string que contiene letras de la A a la Z se puede codificar en números usando el siguiente mapeo:

‘A’ -> “1” 
‘B’ -> “2” 
‘C’ -> “3” 
‘D’ -> “4” 
… 
… 
‘Z’ -> “26” 
Nota: Los caracteres que incluyen el 0 no están incluidos en el problema como (J → 10) .

Ejemplos: 

Entrada: s = “*”
Salida: 9
Explicación: El mensaje codificado puede representar cualquiera de los mensajes codificados “1”, “2”, “3”, “4”, “5”, “6”, “7”, “8” o “9”.
Cada uno de estos se puede decodificar en las strings «A», «B», «C», «D», «E», «F», «G», «H» e «I» respectivamente.
Por lo tanto, hay un total de 9 formas de decodificar «*».

Entrada: s = “1*”
Salida: 18
Explicación: El mensaje codificado puede representar cualquiera de los mensajes codificados “11”, “12”, “13”, “14”, “15”, “16”, “17” , “18” o “19”.
Cada uno de estos mensajes codificados tiene 2 formas de decodificarse (por ejemplo, «11» se puede decodificar como «AA» o «K»).
Por lo tanto, hay un total de 9 × 2 = 18 formas de decodificar «1*». 

Acercarse: 

Este problema se puede resolver observando que cualquier número constante se puede decodificar en un carácter que es un número de un solo dígito o se puede decodificar en un número de dos dígitos si el (i-1)-ésimo carácter es ‘1’ o ( i-1) el carácter es ‘2’ y el i-ésimo carácter está entre 1 y 6. Por lo tanto, el estado actual depende del estado anterior y se puede utilizar la programación dinámica para resolver el problema. Siga los pasos a continuación para resolver el problema: 

1. Sea dp[i] el número de formas de decodificar los caracteres de la string de 0 a i .

2. Si el i-ésimo carácter es ‘*’:

  • dp[i] = dp[i-1]*9 considerando ‘*’ puede ser de 1 a 9 , y se considera solo como un carácter.
  • Ahora, si los caracteres i e i-1 se combinan, entonces,
    • Si el (i-1)ésimo carácter es ‘*’, entonces los dos «**» juntos pueden formar 15 caracteres posibles (como 13 formarán el carácter ‘M’), por lo que sumamos 15×dp[i-2] a dp[ yo] .
    • Si el (i-1)-ésimo carácter es ‘1’, entonces dp[i] = dp[i] + 9×dp[i-2] porque los posibles caracteres que se pueden decodificar serán del 11 al 19 (K a S).
    • Si el carácter (i-1) es ‘2’, entonces dp[i] = dp[i] + 6×dp[i-2] ya que puede tomar valores de 21 a 26.

3. Si el i-ésimo carácter no es ‘*’:

  • dp[i] = dp[i] + dp[i-1] considerando i- ésimo carácter solo como un número.
  • Ahora, si es posible combinar (i-1) el carácter enésimo y el carácter enésimo, entonces agregue dp[i-2] a dp[i].

A continuación se muestra la implementación del enfoque anterior: 

C++

#include <bits/stdc++.h>
using namespace std;
 
int M = 1000000007;
int waysOfDecoding(string s)
{
 
    vector<int> dp((int)s.size()+1);
    dp[0] = 1;
 
    // check the first character of the string
    // if it is '*' then 9 ways
 
    dp[1] = s[0] == '*'
                ? 9
                : s[0] == '0' ? 0 : 1;
 
    // traverse the string
    for (int i = 1; i < (int)s.size(); i++) {
 
        // If s[i] == '*' there can be
        // 9 possible values of *
        if (s[i] == '*') {
            dp[i + 1] = 9 * dp[i];
 
            // If previous character is 1
            // then words that can be formed
            // are K(11), L(12), M(13), N(14)
            // O(15), P(16), Q(17), R(18), S(19)
            if (s[i - 1] == '1')
                dp[i + 1]
                    = (dp[i + 1] + 9 * dp[i - 1]) % M;
 
            // If previous character is 2
            // then the words that can be formed
            // are U(21), V(22), W(23), X(24)Y(25), Z(26)
            else if (s[i - 1] == '2')
                dp[i + 1]
                    = (dp[i + 1] + 6 * dp[i - 1]) % M;
 
            // If the previous digit is * then
            // all 15 2- digit characters can be
            // formed
            else if (s[i - 1] == '*')
                dp[i + 1]
                    = (dp[i + 1] + 15 * dp[i - 1]) % M;
        }
        else {
            // taking the value from previous step
            dp[i + 1] = s[i] != '0' ? dp[i] : 0;
 
            // If previous character is 1 then
            // the i-1th character and ith
            // character can be decoded in
            // a single character therefore,
            // adding dp[i-1].
            if (s[i - 1] == '1')
                dp[i + 1]
                    = (dp[i + 1] + dp[i - 1])
                      % M;
 
            // If previous character is 2
            // and ith character is less than
            // 6
            // then the i-1th character and
            // ith character can be decoded in
            // a single character therefore,
            // adding dp[i-1].
            else if (s[i - 1] == '2'
                     && s[i] <= '6')
                dp[i + 1]
                    = (dp[i + 1] + dp[i - 1]) % M;
 
            // If previous character is * then
            // it will contain the above 2 cases
            else if (s[i - 1] == '*')
                dp[i + 1]
                    = (dp[i + 1]
                       + (s[i] <= '6' ? 2 : 1)
                             * dp[i - 1])
                      % M;
        }
    }
    return dp[(int)s.size()];
}
 
int main()
{
  string s = "12";
  cout<<waysOfDecoding(s);
 
  return 0;
}
 
// This code is contributed by mohit kumar 29.

Java

// Java program for the above approach
 
import java.io.*;
 
class GFG {
    static int M = 1000000007;
    static int waysOfDecoding(String s)
    {
 
        long[] dp = new long[s.length() + 1];
        dp[0] = 1;
 
        // check the first character of the string
        // if it is '*' then 9 ways
 
        dp[1] = s.charAt(0) == '*'
                    ? 9
                    : s.charAt(0) == '0' ? 0 : 1;
 
        // traverse the string
        for (int i = 1; i < s.length(); i++) {
 
            // If s[i] == '*' there can be
            // 9 possible values of *
            if (s.charAt(i) == '*') {
                dp[i + 1] = 9 * dp[i];
 
                // If previous character is 1
                // then words that can be formed
                // are K(11), L(12), M(13), N(14)
                // O(15), P(16), Q(17), R(18), S(19)
                if (s.charAt(i - 1) == '1')
                    dp[i + 1]
                        = (dp[i + 1] + 9 * dp[i - 1]) % M;
 
                // If previous character is 2
                // then the words that can be formed
                // are U(21), V(22), W(23), X(24)Y(25), Z(26)
                else if (s.charAt(i - 1) == '2')
                    dp[i + 1]
                        = (dp[i + 1] + 6 * dp[i - 1]) % M;
 
                // If the previous digit is * then
                // all 15 2- digit characters can be
                // formed
                else if (s.charAt(i - 1) == '*')
                    dp[i + 1]
                        = (dp[i + 1] + 15 * dp[i - 1]) % M;
            }
            else {
                // taking the value from previous step
                dp[i + 1] = s.charAt(i) != '0' ? dp[i] : 0;
 
                // If previous character is 1 then
                // the i-1th character and ith
                // character can be decoded in
                // a single character therefore,
                // adding dp[i-1].
                if (s.charAt(i - 1) == '1')
                    dp[i + 1]
                        = (dp[i + 1] + dp[i - 1])
                          % M;
 
                // If previous character is 2
                // and ith character is less than
                // 6
                // then the i-1th character and
                // ith character can be decoded in
                // a single character therefore,
                // adding dp[i-1].
                else if (s.charAt(i - 1) == '2'
                         && s.charAt(i) <= '6')
                    dp[i + 1]
                        = (dp[i + 1] + dp[i - 1]) % M;
 
                // If previous character is * then
                // it will contain the above 2 cases
                else if (s.charAt(i - 1) == '*')
                    dp[i + 1]
                        = (dp[i + 1]
                           + (s.charAt(i) <= '6' ? 2 : 1)
                                 * dp[i - 1])
                          % M;
            }
        }
        return (int)dp[s.length()];
    }
    public static void main(String[] args)
    {
        String s = "12";
        System.out.println(waysOfDecoding(s));
    }
}

Python3

# Python program for the above approach
M = 1000000007
def waysOfDecoding(s):
 
    dp = [0]*(len(s)+1)
    dp[0] = 1
 
    # check the first character of the string
    # if it is '*' then 9 ways
    if s[0] == '*':
        dp[1] = 9
    elif s[0] == '0':
        dp[1] = 0
    else:
        dp[1] = 1
 
    # traverse the string
    for i in range(len(s)):
 
        # If s[i] == '*' there can be
        # 9 possible values of *
        if (s[i] == '*'):
            dp[i + 1] = 9 * dp[i]
 
            # If previous character is 1
            # then words that can be formed
            # are K(11), L(12), M(13), N(14)
            # O(15), P(16), Q(17), R(18), S(19)
            if (s[i - 1] == '1'):
                dp[i + 1] = (dp[i + 1] + 9 * dp[i - 1]) % M
 
            # If previous character is 2
            # then the words that can be formed
            # are U(21), V(22), W(23), X(24)Y(25), Z(26)
            elif (s[i - 1] == '2'):
                dp[i + 1] = (dp[i + 1] + 6 * dp[i - 1]) % M
 
            # If the previous digit is * then
            # all 15 2- digit characters can be
            # formed
            elif (s[i - 1] == '*'):
                dp[i + 1] = (dp[i + 1] + 15 * dp[i - 1]) % M
 
        else:
            # taking the value from previous step
            if s[i] != '0':
                dp[i+1] = dp[i]
            else:
                dp[i+1] = 0
 
            # If previous character is 1 then
            # the i-1th character and ith
            # character can be decoded in
            # a single character therefore,
            # adding dp[i-1].
            if (s[i - 1] == '1'):
                dp[i + 1] = (dp[i + 1] + dp[i - 1]) % M
 
            # If previous character is 2
            # and ith character is less than
            # 6
            # then the i-1th character and
            # ith character can be decoded in
            # a single character therefore,
            # adding dp[i-1].
            elif (s[i - 1] == '2'
                  and s[i] <= '6'):
                dp[i + 1] = (dp[i + 1] + dp[i - 1]) % M
 
            # If previous character is * then
            # it will contain the above 2 cases
            elif (s[i - 1] == '*'):
                if (s[i] <= '6'):
                    dp[i + 1] = dp[i + 1] + 2 * dp[i - 1]
                else:
                    dp[i + 1] = dp[i + 1] + 1 * dp[i - 1]
 
                dp[i+1] = dp[i+1] % M
 
    return dp[len(s)]
 
 
if __name__ == "__main__":
 
    s = "12"
    print(waysOfDecoding(s))
 
    # This code is contributed by ukasp.

C#

// C# program for the above approach
using System;
 
class GFG{
     
static int M = 1000000007;
static int waysOfDecoding(String s)
{
    long[] dp = new long[s.Length + 1];
    dp[0] = 1;
 
    // Check the first character of the string
    // if it is '*' then 9 ways
    dp[1] = s[0] == '*' ? 9 : s[0] == '0' ? 0 : 1;
 
    // Traverse the string
    for(int i = 1; i < s.Length; i++)
    {
         
        // If s[i] == '*' there can be
        // 9 possible values of *
        if (s[i] == '*')
        {
            dp[i + 1] = 9 * dp[i];
 
            // If previous character is 1
            // then words that can be formed
            // are K(11), L(12), M(13), N(14)
            // O(15), P(16), Q(17), R(18), S(19)
            if (s[i - 1] == '1')
                dp[i + 1] = (dp[i + 1] + 9 *
                             dp[i - 1]) % M;
 
            // If previous character is 2
            // then the words that can be formed
            // are U(21), V(22), W(23), X(24)Y(25),
            // Z(26)
            else if (s[i - 1] == '2')
                dp[i + 1] = (dp[i + 1] + 6 *
                             dp[i - 1]) % M;
 
            // If the previous digit is * then
            // all 15 2- digit characters can be
            // formed
            else if (s[i - 1] == '*')
                dp[i + 1] = (dp[i + 1] + 15 *
                             dp[i - 1]) % M;
        }
        else
        {
             
            // Taking the value from previous step
            dp[i + 1] = s[i] != '0' ? dp[i] : 0;
 
            // If previous character is 1 then
            // the i-1th character and ith
            // character can be decoded in
            // a single character therefore,
            // adding dp[i-1].
            if (s[i - 1] == '1')
                dp[i + 1] = (dp[i + 1] + dp[i - 1]) % M;
 
            // If previous character is 2
            // and ith character is less than
            // 6
            // then the i-1th character and
            // ith character can be decoded in
            // a single character therefore,
            // adding dp[i-1].
            else if (s[i - 1] == '2' && s[i] <= '6')
                dp[i + 1] = (dp[i + 1] + dp[i - 1]) % M;
 
            // If previous character is * then
            // it will contain the above 2 cases
            else if (s[i - 1] == '*')
                dp[i + 1] = (dp[i + 1] + (s[i] <= '6' ? 2 : 1) *
                             dp[i - 1]) % M;
        }
    }
    return (int)dp[s.Length];
}
 
// Driver code
public static void Main()
{
    String s = "12";
    Console.WriteLine(waysOfDecoding(s));
}
}
 
// This code is contributed by rishavmahato348

Javascript

<script>
// Javascript program for the above approach
 
let M = 1000000007;
function waysOfDecoding(s)
{
    let dp = new Array(s.length + 1);
    for(let i=0;i<s.length+1;i++)
        dp[i] = 0;
        dp[0] = 1;
  
        // check the first character of the string
        // if it is '*' then 9 ways
  
        dp[1] = s[0] == '*'
                    ? 9
                    : s[0] == '0' ? 0 : 1;
  
        // traverse the string
        for (let i = 1; i < s.length; i++) {
  
            // If s[i] == '*' there can be
            // 9 possible values of *
            if (s[i] == '*') {
                dp[i + 1] = 9 * dp[i];
  
                // If previous character is 1
                // then words that can be formed
                // are K(11), L(12), M(13), N(14)
                // O(15), P(16), Q(17), R(18), S(19)
                if (s[i-1] == '1')
                    dp[i + 1]
                        = (dp[i + 1] + 9 * dp[i - 1]) % M;
  
                // If previous character is 2
                // then the words that can be formed
                // are U(21), V(22), W(23), X(24)Y(25), Z(26)
                else if (s[i-1] == '2')
                    dp[i + 1]
                        = (dp[i + 1] + 6 * dp[i - 1]) % M;
  
                // If the previous digit is * then
                // all 15 2- digit characters can be
                // formed
                else if (s[i-1] == '*')
                    dp[i + 1]
                        = (dp[i + 1] + 15 * dp[i - 1]) % M;
            }
            else {
                // taking the value from previous step
                dp[i + 1] = s[i] != '0' ? dp[i] : 0;
  
                // If previous character is 1 then
                // the i-1th character and ith
                // character can be decoded in
                // a single character therefore,
                // adding dp[i-1].
                if (s[i-1] == '1')
                    dp[i + 1]
                        = (dp[i + 1] + dp[i - 1])
                          % M;
  
                // If previous character is 2
                // and ith character is less than
                // 6
                // then the i-1th character and
                // ith character can be decoded in
                // a single character therefore,
                // adding dp[i-1].
                else if (s[i-1] == '2'
                         && s[i] <= '6')
                    dp[i + 1]
                        = (dp[i + 1] + dp[i - 1]) % M;
  
                // If previous character is * then
                // it will contain the above 2 cases
                else if (s[i-1] == '*')
                    dp[i + 1]
                        = (dp[i + 1]
                           + (s[i] <= '6' ? 2 : 1)
                                 * dp[i - 1])
                          % M;
            }
        }
        return dp[s.length];
}
 
let s = "12";
document.write(waysOfDecoding(s));
 
// This code is contributed by unknown2108
</script>
Producción

2

Complejidad temporal: O(n)
Espacio auxiliar: O(n)

Optimización adicional del espacio 

Si se observa cuidadosamente el código anterior, se observa que el valor de dp[i] se encuentra usando dp[i-1] y dp[i-2] . Entonces, para optimizar aún más el espacio, en lugar de crear una array de dp de longitud N , podemos usar tres variables: segundo (almacena el valor de dp[i] ), primero (almacena el valor de dp[i-2] ), y temp (almacena el valor de dp[i-1] ). Entonces, después de encontrar el valor del segundo (dp [i]) , modifique primero = temperatura y temperatura = segundoy luego calcule nuevamente el valor de second(dp[i]) usando la variable first y temp

C++

// C++ program for the above approach
#include <bits/stdc++.h>
using namespace std;
 
int M = 1000000007;
int waysOfDecoding(string s)
{
    long first = 1,
    second = s[0] == '*' ? 9 : s[0] == '0' ? 0 : 1;
     
    for(int i = 1; i < s.size(); i++)
    {
        long temp = second;
 
        // If s[i] == '*' there can be
        // 9 possible values of *
        if (s[i] == '*')
        {
            second = 9 * second;
             
            // If previous character is 1
            // then words that can be formed
            // are K(11), L(12), M(13), N(14)
            // O(15), P(16), Q(17), R(18), S(19)
            if (s[i - 1] == '1')
                second = (second + 9 * first) % M;
 
            // If previous character is 2
            // then the words that can be formed
            // are U(21), V(22), W(23), X(24)Y(25), Z(26)
            else if (s[i - 1] == '2')
                second = (second + 6 * first) % M;
 
            // If the previous digit is * then
            // all 15 2- digit characters can be
            // formed
            else if (s[i - 1] == '*')
                second = (second + 15 * first) % M;
        }
         
        // If s[i] != '*'
        else
        {
            second = s[i] != '0' ? second : 0;
 
            // Adding first in second
            // if s[i-1]=1
            if (s[i - 1] == '1')
                second = (second + first) % M;
 
            // Adding first in second if
            // s[i-1] == 2 and s[i]<='6'
            else if (s[i - 1] == '2' && s[i] <= '6')
                second = (second + first) % M;
 
            // If s[i-1] == '*' the union
            // of above 2 cases has to be done
            else if (s[i - 1] == '*')
                second = (second + (s[i] <= '6' ? 2 : 1) *
                          first) % M;
        }
        first = temp;
    }
    return(int)second;
}
 
// Driver code
int main()
{
    string s = "*";
    cout << waysOfDecoding(s);
    return 0;
}
 
// This code is contributed by rishavmahato348

Java

// Java program for the above approach
import java.io.*;
 
class GFG {
    static int M = 1000000007;
    static int waysOfDecoding(String s)
    {
        long first = 1, second
                        = s.charAt(0) == '*'
                              ? 9
                              : s.charAt(0) == '0' ? 0 : 1;
        for (int i = 1; i < s.length(); i++) {
            long temp = second;
 
            // If s[i] == '*' there can be
            // 9 possible values of *
            if (s.charAt(i) == '*') {
                second = 9 * second;
 
                // If previous character is 1
                // then words that can be formed
                // are K(11), L(12), M(13), N(14)
                // O(15), P(16), Q(17), R(18), S(19)
                if (s.charAt(i - 1) == '1')
                    second = (second + 9 * first) % M;
 
                // If previous character is 2
                // then the words that can be formed
                // are U(21), V(22), W(23), X(24)Y(25), Z(26)
                else if (s.charAt(i - 1) == '2')
                    second = (second + 6 * first) % M;
 
                // If the previous digit is * then
                // all 15 2- digit characters can be
                // formed
                else if (s.charAt(i - 1) == '*')
                    second = (second + 15 * first) % M;
            }
            // If s[i] != '*'
            else {
                second = s.charAt(i) != '0' ? second : 0;
 
                // Adding first in second
                // if s[i-1]=1
                if (s.charAt(i - 1) == '1')
                    second = (second + first) % M;
 
                // Adding first in second if
                // s[i-1] == 2 and s[i]<='6'
                else if (s.charAt(i - 1) == '2'
                         && s.charAt(i) <= '6')
                    second = (second + first) % M;
 
                // if s[i-1] == '*' the union
                // of above 2 cases has to be done
                else if (s.charAt(i - 1) == '*')
                    second = (second
                              + (s.charAt(i) <= '6' ? 2 : 1)
                                    * first)
                             % M;
            }
            first = temp;
        }
        return (int)second;
    }
    public static void main(String[] args)
    {
        String s = "*";
        System.out.println(waysOfDecoding(s));
    }
}

Python3

# Python program for the above approach
M = 1000000007
def waysOfDecoding(s):
 
    first = 1
    second = 9 if(s[0] == '*') else(0 if(s[0] == '0') else 1)
 
    for i in range(1,len(s)):
 
        temp = second
 
        # If s[i] == '*' there can be
        # 9 possible values of *
        if (s[i] == '*'):
            second = 9 * second
 
            # If previous character is 1
            # then words that can be formed
            # are K(11), L(12), M(13), N(14)
            # O(15), P(16), Q(17), R(18), S(19)
            if (s[i - 1] == '1'):
                second = (second + 9 * first) % M
 
            # If previous character is 2
            # then the words that can be formed
            # are U(21), V(22), W(23), X(24)Y(25), Z(26)
            elif (s[i - 1] == '2'):
                second = (second + 6 * first) % M
 
            # If the previous digit is * then
            # all 15 2- digit characters can be
            # formed
            elif (s[i - 1] == '*'):
                second = (second + 15 * first) % M
         
        # If s[i] != '*'
        else:
 
            second = second if(s[i] != '0') else 0
 
            # Adding first in second
            # if s[i-1]=1
            if (s[i - 1] == '1'):
                second = (second + first) % M
 
            # Adding first in second if
            # s[i-1] == 2 and s[i]<=l          
            elif (s[i - 1] == '2' and s[i] <= '6'):
                second = (second + first) % M
 
            # if s[i-1] == '*' the union
            # of above 2 cases has to be done
            elif (s[i - 1] == '*'):
                second = (second + (2 if(s[i] <= '6') else 1) * first) % M
        first = temp
    return second
 
# Driver Code
s = "*"
 
print(waysOfDecoding(s))
 
# This code is contributed by shinjanpatra

C#

// C# program for the above approach
using System;
 
class GFG{
     
static int M = 1000000007;
 
static int waysOfDecoding(string s)
{
    long first = 1,
    second = s[0] == '*' ? 9 : s[0] == '0' ? 0 : 1;
    for(int i = 1; i < s.Length; i++)
    {
        long temp = second;
 
        // If s[i] == '*' there can be
        // 9 possible values of *
        if (s[i] == '*')
        {
            second = 9 * second;
 
            // If previous character is 1
            // then words that can be formed
            // are K(11), L(12), M(13), N(14)
            // O(15), P(16), Q(17), R(18), S(19)
            if (s[i - 1] == '1')
                second = (second + 9 * first) % M;
 
            // If previous character is 2
            // then the words that can be formed
            // are U(21), V(22), W(23), X(24)Y(25), Z(26)
            else if (s[i - 1] == '2')
                second = (second + 6 * first) % M;
 
            // If the previous digit is * then
            // all 15 2- digit characters can be
            // formed
            else if (s[i - 1] == '*')
                second = (second + 15 * first) % M;
        }
         
        // If s[i] != '*'
        else
        {
            second = s[i] != '0' ? second : 0;
 
            // Adding first in second
            // if s[i-1]=1
            if (s[i - 1] == '1')
                second = (second + first) % M;
 
            // Adding first in second if
            // s[i-1] == 2 and s[i]<='6'
            else if (s[i - 1] == '2' && s[i] <= '6')
                second = (second + first) % M;
 
            // if s[i-1] == '*' the union
            // of above 2 cases has to be done
            else if (s[i - 1] == '*')
                second = (second + (s[i] <= '6' ? 2 : 1) *
                          first) % M;
        }
        first = temp;
    }
    return (int)second;
}
 
// Driver code
static public void Main()
{
    string s = "*";
     
    Console.WriteLine(waysOfDecoding(s));
}
}
 
// This code is contributed by patel2127

Javascript

<script>
 
// JavaScript program for the above approach
let M = 1000000007;
 
function waysOfDecoding(s)
{
    let first = 1,
    second = s[0] == '*' ? 9 : s[0] == '0' ? 0 : 1;
    for(let i = 1; i < s.length; i++)
    {
        let temp = second;
 
        // If s[i] == '*' there can be
        // 9 possible values of *
        if (s[i] == '*')
        {
            second = 9 * second;
 
            // If previous character is 1
            // then words that can be formed
            // are K(11), L(12), M(13), N(14)
            // O(15), P(16), Q(17), R(18), S(19)
            if (s[i - 1] == '1')
                second = (second + 9 * first) % M;
 
            // If previous character is 2
            // then the words that can be formed
            // are U(21), V(22), W(23), X(24)Y(25), Z(26)
            else if (s[i - 1] == '2')
                second = (second + 6 * first) % M;
 
            // If the previous digit is * then
            // all 15 2- digit characters can be
            // formed
            else if (s[i - 1] == '*')
                second = (second + 15 * first) % M;
        }
         
        // If s[i] != '*'
        else
        {
            second = s[i] != '0' ? second : 0;
 
            // Adding first in second
            // if s[i-1]=1
            if (s[i - 1] == '1')
                second = (second + first) % M;
 
            // Adding first in second if
            // s[i-1] == 2 and s[i]<='6'
            else if (s[i - 1] == '2' && s[i] <= '6')
                second = (second + first) % M;
 
            // if s[i-1] == '*' the union
            // of above 2 cases has to be done
            else if (s[i - 1] == '*')
                second = (second + (s[i] <= '6' ? 2 : 1) *
                          first) % M;
        }
        first = temp;
    }
    return second;
}
 
// Driver Code
let s = "*";
 
document.write(waysOfDecoding(s));
 
// This code is contributed by code_hunt
 
</script>
Producción

9

Complejidad temporal: O(n)
Espacio auxiliar: O(1)

Publicación traducida automáticamente

Artículo escrito por TanmayChakraborty y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA

Deja una respuesta

Tu dirección de correo electrónico no será publicada. Los campos obligatorios están marcados con *