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