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>
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>
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