Contar posibles decodificaciones de una secuencia de dígitos dada

Deje que 1 represente ‘A’, 2 represente ‘B’, etc. Dada una secuencia de dígitos, cuente el número de posibles decodificaciones de la secuencia de dígitos dada. 

Ejemplos: 

Input:  digits[] = "121"
Output: 3
// The possible decodings are "ABA", "AU", "LA"

Input: digits[] = "1234"
Output: 3
// The possible decodings are "ABCD", "LCD", "AWD"

Se considera que una secuencia de dígitos vacía tiene una decodificación. Se puede suponer que la entrada contiene dígitos válidos del 0 al 9 y que no hay ceros iniciales, ceros finales adicionales ni dos o más ceros consecutivos.

Este problema es recursivo y se puede dividir en subproblemas. Comenzamos desde el final de la secuencia de dígitos dada. Inicializamos el recuento total de decodificaciones como 0. Repetimos para dos subproblemas. 
1) Si el último dígito no es cero, recurra a los dígitos restantes (n-1) y sume el resultado al conteo total. 
2) Si los dos últimos dígitos forman un carácter válido (o menor que 27), recurra a los dígitos restantes (n-2) y sume el resultado al conteo total.

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

C++

// C++ implementation to count number of
// decodings that can be formed from a
// given digit sequence
#include <cstring>
#include <iostream>
using namespace std;
 
// recurring function to find
// ways in how many ways a
// string can be decoded of length
// greater than 0 and starting with
// digit 1 and greater.
int countDecoding(char* digits, int n)
{
    // base cases
    if (n == 0 || n == 1)
        return 1;
    if (digits[0] == '0')
        return 0;
 
    // for base condition "01123" should return 0
    // Initialize count
    int count = 0;
 
    // If the last digit is not 0,
    // then last digit must add
    // to the number of words
    if (digits[n - 1] > '0')
        count = countDecoding(digits, n - 1);
 
    // If the last two digits form a number smaller
    // than or equal to 26, then consider
    // last two digits and recur
    if (digits[n - 2] == '1'
        || (digits[n - 2] == '2'
        && digits[n - 1] < '7'))
        count += countDecoding(digits, n - 2);
 
    return count;
}
 
// Given a digit sequence of length n,
// returns count of possible decodings by
// replacing 1 with A, 2 with B, ... 26 with Z
int countWays(char* digits, int n)
{
    if (n == 0 || (n == 1 && digits[0] == '0'))
        return 0;
    return countDecoding(digits, n);
}
 
// Driver code
int main()
{
    char digits[] = "1234";
    int n = strlen(digits);
    cout << "Count is " << countWays(digits, n);
    return 0;
}
// Modified by Atanu Sen

Java

// A naive recursive Java implementation
// to count number of decodings that
// can be formed from a given digit sequence
 
class GFG {
 
    // recurring function to find
    // ways in how many ways a
    // string can be decoded of length
    // greater than 0 and starting with
    // digit 1 and greater.
    static int countDecoding(char[] digits, int n)
    {
        // base cases
        if (n == 0 || n == 1)
            return 1;
 
        // for base condition "01123" should return 0
        if (digits[0] == '0')
            return 0;
 
        // Initialize count
        int count = 0;
 
        // If the last digit is not 0, then
        // last digit must add to
        // the number of words
        if (digits[n - 1] > '0')
            count = countDecoding(digits, n - 1);
 
        // If the last two digits form a number
        // smaller than or equal to 26,
        // then consider last two digits and recur
        if (digits[n - 2] == '1'
            || (digits[n - 2] == '2'
                && digits[n - 1] < '7'))
            count += countDecoding(digits, n - 2);
 
        return count;
    }
 
    // Given a digit sequence of length n,
    // returns count of possible decodings by
    // replacing 1 with A, 2 with B, ... 26 with Z
    static int countWays(char[] digits, int n)
    {
        if (n == 0 || (n == 1 && digits[0] == '0'))
            return 0;
        return countDecoding(digits, n);
    }
 
    // Driver code
    public static void main(String[] args)
    {
        char digits[] = { '1', '2', '3', '4' };
        int n = digits.length;
        System.out.printf("Count is %d",
                          countWays(digits, n));
    }
}
 
// This code is contributed by Smitha Dinesh Semwal.
// Modified by Atanu Sen

Python3

# Recursive implementation of numDecodings
def numDecodings(s: str) -> int:
    if len(s) == 0
    or (len(s) == 1
        and s[0] == '0'):
        return 0
    return numDecodingsHelper(s, len(s))
 
 
def numDecodingsHelper(s: str, n: int) -> int:
    if n == 0 or n == 1:
        return 1
    count = 0
    if s[n-1] > "0":
        count = numDecodingsHelper(s, n-1)
    if (s[n - 2] == '1'
        or (s[n - 2] == '2'
            and s[n - 1] < '7')):
        count += numDecodingsHelper(s, n - 2)
    return count
 
 
# Driver code
digits = "1234"
print("Count is ", numDecodings(digits))
# This code is contributed by Frank Hu

C#

// A naive recursive C# implementation
// to count number of decodings that
// can be formed from a given digit sequence
using System;
 
class GFG {
 
    // recurring function to find
    // ways in how many ways a
    // string can be decoded of length
    // greater than 0 and starting with
    // digit 1 and greater.
    static int countDecoding(char[] digits, int n)
    {
 
        // base cases
        if (n == 0 || n == 1)
            return 1;
 
        // Initialize count
        int count = 0;
 
        // If the last digit is not 0, then
        // last digit must add to
        // the number of words
        if (digits[n - 1] > '0')
            count = countDecoding(digits, n - 1);
 
        // If the last two digits form a number
        // smaller than or equal to 26, then
        // consider last two digits and recur
        if (digits[n - 2] == '1'
            || (digits[n - 2] == '2'
                && digits[n - 1] < '7'))
            count += countDecoding(digits, n - 2);
 
        return count;
    }
 
    // Given a digit sequence of length n,
    // returns count of possible decodings by
    // replacing 1 with A, 2 with B, ... 26 with Z
    static int countWays(char[] digits, int n)
    {
        if (n == 0 || (n == 1 && digits[0] == '0'))
            return 0;
        return countDecoding(digits, n);
    }
 
    // Driver code
    public static void Main()
    {
        char[] digits = { '1', '2', '3', '4' };
        int n = digits.Length;
        Console.Write("Count is ");
        Console.Write(countWays(digits, n));
    }
}
 
// This code is contributed by nitin mittal.

PHP

<?php
// A naive recursive PHP implementation
// to count number of decodings that can
// be formed from a given digit sequence
 
//recurring function to find
//ways in how many ways a
//string can be decoded of length
//greater than 0 and starting with
//digit 1 and greater.
function countDecoding(&$digits, $n)
{
    // base cases
    if ($n == 0 || $n == 1)
        return 1;
 
    $count = 0; // Initialize count
 
    // If the last digit is not 0, then last
    // digit must add to the number of words
    if ($digits[$n - 1] > '0')
        $count = countDecoding($digits, $n - 1);
 
    // If the last two digits form a number
    // smaller than or equal to 26, then
    // consider last two digits and recur
    if ($digits[$n - 2] == '1' ||
       ($digits[$n - 2] == '2' &&
        $digits[$n - 1] < '7') )
        $count += countDecoding($digits, $n - 2);
 
    return $count;
}
 
// Given a digit sequence of length n,
// returns count of possible decodings by
// replacing 1 with A, 2 with B, ... 26 with Z
function countWays(&$digits, $n){
  if($n==0 || ($n == 1 && $digits[0] == '0'))
     return 0;
  return countDecoding($digits, $n);
}
 
// Driver Code
$digits = "1234";
$n = strlen($digits);
echo "Count is " . countWays($digits, $n);
 
// This code is contributed by ita_c
?>

Javascript

<script>
 
// A naive recursive JavaScript implementation
// to count number of decodings that
// can be formed from a given digit sequence   
     
    // recurring function to find
    // ways in how many ways a
    // string can be decoded of length
    // greater than 0 and starting with
    // digit 1 and greater.
    function countDecoding(digits, n)
    {
        // base cases
        if (n == 0 || n == 1)
        {
            return 1;
        }
        // for base condition "01123" should return 0
        if (digits[0] == '0')
        {
            return 0;
        }
         
        // Initialize count
        let count = 0;
         
        // If the last digit is not 0, then
        // last digit must add to
        // the number of words
        if (digits[n - 1] > '0')
        {
            count = countDecoding(digits, n - 1);
        }
        // If the last two digits form a number
        // smaller than or equal to 26,
        // then consider last two digits and recur
        if (digits[n - 2] == '1'
            || (digits[n - 2] == '2'
                && digits[n - 1] < '7'))
        {
            count += countDecoding(digits, n - 2);
        }
        return count;
    }
    // Given a digit sequence of length n,
    // returns count of possible decodings by
    // replacing 1 with A, 2 with B, ... 26 with Z
    function countWays(digits, n)
    {
        if (n == 0 || (n == 1 && digits[0] == '0'))
        {
            return 0;
        }
        return countDecoding(digits, n);
    }
     
    // Driver code
    digits=['1', '2', '3', '4'];
    let n = digits.length;
    document.write("Count is ",countWays(digits, n));
     
    // This code is contributed by avanitrachhadiya2155
     
</script>

Producción: 

Count is 3

La complejidad temporal del código anterior es exponencial. Si observamos más de cerca el programa anterior, podemos observar que la solución recursiva es similar a los números de Fibonacci . Por lo tanto, podemos optimizar la solución anterior para trabajar en tiempo O(n) usando Programación Dinámica

A continuación se muestra la implementación del mismo. 

C++

// A Dynamic Programming based C++
// implementation to count decodings
#include <iostream>
#include <cstring>
using namespace std;
 
// A Dynamic Programming based function
// to count decodings
int countDecodingDP(char *digits, int n)
{
    // A table to store results of subproblems
    int count[n+1];
    count[0] = 1;
    count[1] = 1;
    //for base condition "01123" should return 0
    if(digits[0]=='0') 
         return 0;
    for (int i = 2; i <= n; i++)
    {
        count[i] = 0;
 
        // If the last digit is not 0,
        // then last digit must add to the number of words
        if (digits[i-1] > '0')
            count[i] = count[i-1];
 
        // If second last digit is smaller
        // than 2 and last digit is smaller than 7,
        // then last two digits form a valid character
        if (digits[i-2] == '1' ||
              (digits[i-2] == '2' && digits[i-1] < '7') )
            count[i] += count[i-2];
    }
    return count[n];
}
 
// Driver program to test above function
int main()
{
    char digits[] = "1234";
    int n = strlen(digits);
    cout << "Count is " << countDecodingDP(digits, n);
    return 0;
}
// Modified by Atanu Sen

Java

// A Dynamic Programming based Java
// implementation to count decodings
import java.io.*;
 
class GFG
{
     
// A Dynamic Programming based
// function to count decodings
static int countDecodingDP(char digits[],
                           int n)
{
    // A table to store results of subproblems
    int count[] = new int[n + 1];
    count[0] = 1;
    count[1] = 1;
    if(digits[0]=='0')   //for base condition "01123" should return 0
          return 0;
    for (int i = 2; i <= n; i++)
    {
        count[i] = 0;
 
        // If the last digit is not 0,
        // then last digit must add to
        // the number of words
        if (digits[i - 1] > '0')
            count[i] = count[i - 1];
 
        // If second last digit is smaller
        // than 2 and last digit is smaller
        // than 7, then last two digits
        // form a valid character
        if (digits[i - 2] == '1' ||
           (digits[i - 2] == '2' &&
            digits[i - 1] < '7'))
            count[i] += count[i - 2];
    }
    return count[n];
}
 
// Driver Code
public static void main (String[] args)
{
    char digits[] = {'1','2','3','4'};
    int n = digits.length;
    System.out.println("Count is " +
               countDecodingDP(digits, n));
}
}
 
// This code is contributed by anuj_67
// Modified by Atanu Sen

Python3

# A Dynamic Programming based Python3
# implementation to count decodings
 
# A Dynamic Programming based function
# to count decodings
def countDecodingDP(digits, n):
 
    count = [0] * (n + 1); # A table to store
                           # results of subproblems
    count[0] = 1;
    count[1] = 1;
 
    for i in range(2, n + 1):
 
        count[i] = 0;
 
        # If the last digit is not 0, then last
        # digit must add to the number of words
        if (digits[i - 1] > '0'):
            count[i] = count[i - 1];
 
        # If second last digit is smaller than 2
        # and last digit is smaller than 7, then
        # last two digits form a valid character
        if (digits[i - 2] == '1' or
           (digits[i - 2] == '2' and
            digits[i - 1] < '7') ):
            count[i] += count[i - 2];
 
    return count[n];
 
# Driver Code
digits = "1234";
n = len(digits);
print("Count is" ,
       countDecodingDP(digits, n));
 
# This code is contributed by mits

C#

// A Dynamic Programming based C#
// implementation to count decodings
using System;
 
class GFG
{
     
// A Dynamic Programming based
// function to count decodings
static int countDecodingDP(char[] digits,
                           int n)
{
    // A table to store results of subproblems
    int[] count = new int[n + 1];
    count[0] = 1;
    count[1] = 1;
 
    for (int i = 2; i <= n; i++)
    {
        count[i] = 0;
 
        // If the last digit is not 0,
        // then last digit must add to
        // the number of words
        if (digits[i - 1] > '0')
            count[i] = count[i - 1];
 
        // If second last digit is smaller
        // than 2 and last digit is smaller
        // than 7, then last two digits
        // form a valid character
        if (digits[i - 2] == '1' ||
           (digits[i - 2] == '2' &&
            digits[i - 1] < '7'))
            count[i] += count[i - 2];
    }
    return count[n];
}
 
// Driver Code
public static void Main()
{
    char[] digits = {'1','2','3','4'};
    int n = digits.Length;
    Console.WriteLine("Count is " +
            countDecodingDP(digits, n));
}
}
 
// This code is contributed
// by Akanksha Rai
// Modified by Atanu Sen

PHP

<?php
// A Dynamic Programming based
// php implementation to count decodings
 
// A Dynamic Programming based function to count decodings
function countDecodingDP($digits, $n)
{
    // A table to store results of subproblems
    $count[$n+1]=array();
    $count[0] = 1;
    $count[1] = 1;
 
    for ($i = 2; $i <= $n; $i++)
    {
        $count[$i] = 0;
 
        // If the last digit is not 0, then last digit must add to
        // the number of words
        if ($digits[$i-1] > '0')
            $count[$i] = $count[$i-1];
 
        // If second last digit is smaller than 2 and last digit is
        // smaller than 7, then last two digits form a valid character
        if ($digits[$i-2] == '1' || ($digits[$i-2] == '2' && $digits[$i-1] < '7') )
            $count[$i] += $count[$i-2];
    }
    return $count[$n];
}
 
// Driver program to test above function
    $digits = "1234";
    $n = strlen($digits);
    echo  "Count is " , countDecodingDP($digits, $n);
 
#This code is contributed by ajit.
?>

Javascript

<script>
 
// A Dynamic Programming based Javascript
// implementation to count decodings
 
// A Dynamic Programming based
// function to count decodings
function countDecodingDP(digits, n)
{
     
    // A table to store results of subproblems
    let count = new Array(n + 1);
    count[0] = 1;
    count[1] = 1;
     
    // For base condition "01123" should return 0
    if (digits[0] == '0')  
          return 0;
           
    for(let i = 2; i <= n; i++)
    {
        count[i] = 0;
  
        // If the last digit is not 0,
        // then last digit must add to
        // the number of words
        if (digits[i - 1] > '0')
            count[i] = count[i - 1];
  
        // If second last digit is smaller
        // than 2 and last digit is smaller
        // than 7, then last two digits
        // form a valid character
        if (digits[i - 2] == '1' ||
           (digits[i - 2] == '2' &&
            digits[i - 1] < '7'))
            count[i] += count[i - 2];
    }
    return count[n];
}
 
// Driver Code
let digits = [ '1','2','3','4' ];
let n = digits.length;
 
document.write("Count is " +
               countDecodingDP(digits, n));
                
// This code is contributed by rag2127
     
</script>

Producción: 

Count is 3

La complejidad temporal de la solución anterior es O(n) y requiere espacio auxiliar O(n). Podemos reducir el espacio auxiliar a O(1) usando la versión optimizada para el espacio discutida en la Publicación del número de Fibonacci
Escriba comentarios si encuentra algo incorrecto o si desea compartir más información sobre el tema tratado anteriormente.

Método 3: (DP de arriba hacia abajo)

Acercarse :  

El problema anterior se puede resolver usando Top down DP de la siguiente manera. Una de las intuiciones básicas es que necesitamos encontrar el número total de formas de decodificar la string dada, de modo que todos y cada uno de los números de la string deben estar entre el rango de [1, 26], ambos inclusive y sin ceros a la izquierda. Consideremos una string de ejemplo.

string = «123»

Si observamos cuidadosamente, podemos observar un patrón aquí, es decir, la cantidad de formas en que se puede decodificar una substring en particular depende de la cantidad de formas en que se decodificará la string restante. Por ejemplo, queremos la cantidad de formas de decodificar la string con «1» como prefijo; el resultado depende de la cantidad de formas en que se puede decodificar la string restante, es decir, «23». La cantidad de formas en que se puede decodificar la string «23» son «2», «3» y «23». Hay 2 formas en ambos casos. Solo podemos agregar «1» para obtener la cantidad de formas en que se puede decodificar la string dada. ser decodificado con «1» como prefijo, es decir, «1», «2», «3» y «1», «23». Ahora hemos encontrado la cantidad de formas en que podemos decodificar la string dada con «1» como prefijo, pero «12» también se encuentra entre el rango de [ 1 , 26 ] ambos inclusive, el número de formas de decodificar la string dada con «12» como prefijo depende del resultado de cómo se decodifica la string restante. Aquí, la string restante es «3», se puede decodificar de una sola manera, por lo que podemos agregar «12» delante de la string «3» para obtenerla, es decir, «12», «3». Entonces, el número total de formas en que se puede decodificar la string dada es de 3 formas.

Pero podemos ver algunos de los subproblemas superpuestos aquí, es decir, cuando estamos calculando el número total de formas de decodificar la string «23», estamos calculando el número de formas en que se puede decodificar la string «3», así como cuando estamos calculando el número de formas en que se puede decodificar la string «12». Estamos calculando nuevamente el número de formas en que se puede decodificar la string «3». Entonces podemos evitar esto almacenando el resultado de cada substring. Aquí podemos identificar todos y cada uno de los subproblemas a través del índice de la string. Por lo tanto, si en algún momento ya hemos calculado el número de formas en que se puede decodificar la substring, podemos devolver directamente el resultado y eso conduce a una gran cantidad de optimización.

A continuación se muestra la implementación de C++

C++

#include<bits/stdc++.h>
using namespace std;
 
int mod = 1e9 + 7;
 
// function which returns the number of ways to decode the message
int decodeMessage(vector<int> &dp,int s,string &str,int n)
{
    // an empty string can also form 1 valid decoding
    if(s >= n)
        return 1;
     
    /*
        if we have already computed the number of
        ways to decode the substring return the
        answer directly
    */
    if(dp[s] != -1)
        return dp[s];
     
    int num,tc;
    num = tc = 0;
    for(int i=s;i<n;i++)
    {
        // generate the number
        num = num*10 + (str[i] - '0');
 
        // validate the number
        if(num >= 1 and num <= 26)
        {
            /*
                since the number of ways to decode any string
                depends on the result of
                how the remaining string is decoded so get the
                number of ways how the rest of the string can
                be decoded
            */
            int c = decodeMessage(dp,i+1,str,n);
 
            // add all the ways that the substring
            // from the current index can be decoded
            tc = (tc%mod + c%mod)%mod;
        }
 
        // leading 0’s or the number
        // generated so far is greater than 26
        // we can just stop the process
        // as it can never be a part of our solution
        else
            break;
    }
 
    // store all the possible decodings and return the result
    return (dp[s] = tc);
}
int CountWays(string str)
{
    int n = str.size();
 
    // empty string can form 1 valid decoding
    if(n == 0)
        return 1;
 
    // dp vector to store the  number of ways
    // to decode each and every substring
    vector<int> dp(n,-1);
 
    // return the result
    return decodeMessage(dp,0,str,n);
}
int main()
{
    string str = "1234";
    cout << CountWays(str) << endl;
    return 0;
}

Java

/*package whatever //do not write package name here */
import java.io.*;
 
class GFG {
  static int mod = 1000000007;
 
  // function which returns the number of ways to decode the message
  static int decodeMessage(int[] dp, int s, String str, int n)
  {
     
    // an empty string can also form 1 valid decoding
    if(s >= n)
      return 1;
 
    /*
        if we have already computed the number of
        ways to decode the substring return the
        answer directly
    */
    if(dp[s] != -1)
      return dp[s];
 
    int num,tc;
    num = tc = 0;
    for(int i=s;i<n;i++)
    {
      // generate the number
      num = num*10 + ((int)str.charAt(i) - '0');
 
      // validate the number
      if(num >= 1 && num <= 26)
      {
        /*
                since the number of ways to decode any string
                depends on the result of
                how the remaining string is decoded so get the
                number of ways how the rest of the string can
                be decoded
            */
        int c = decodeMessage(dp, i + 1, str, n);
 
        // add all the ways that the substring
        // from the current index can be decoded
        tc = (tc%mod + c%mod)%mod;
      }
 
      // leading 0’s or the number
      // generated so far is greater than 26
      // we can just stop the process
      // as it can never be a part of our solution
      else
        break;
    }
 
    // store all the possible decodings and return the result
    return (dp[s] = tc);
  }
  static int CountWays(String str)
  {
    int n = str.length();
 
    // empty string can form 1 valid decoding
    if(n == 0)
      return 1;
 
    // dp vector to store the number of ways
    // to decode each and every substring
    int[] dp = new int[n];
    for(int i = 0; i < n; i++){
      dp[i] = -1;
    }
 
    // return the result
    return decodeMessage(dp,0,str,n);
  }
 
  // Driver Code
  public static void main(String args[])
  {
    String str = "1234";
    System.out.println(CountWays(str));
  }
}
 
// This code is contributed by shinjanpatra

Python3

mod = 1e9 + 7
 
# function which returns the number of ways to decode the message
def decodeMessage(dp, s, str, n):
   
    # an empty string can also form 1 valid decoding
    if(s >= n):
        return 1
 
        # if we have already computed the number of
        # ways to decode the substring return the
        # answer directly
 
    if(dp[s] != -1):
        return dp[s]
     
    num = 0
    tc = 0
    for i in range(s,n):
        # generate the number
        num = num*10 + (ord(str[i]) - ord('0'))
 
        # validate the number
        if(num >= 1 and num <= 26):
             
                # since the number of ways to decode any string
                # depends on the result of
                # how the remaining string is decoded so get the
                # number of ways how the rest of the string can
                # be decoded
            c = decodeMessage(dp, i + 1, str, n)
 
            # add all the ways that the substring
            # from the current index can be decoded
            tc = int((tc%mod + c%mod)%mod)
 
        # leading 0’s or the number
        # generated so far is greater than 26
        # we can just stop the process
        # as it can never be a part of our solution
        else:
            break
 
    # store all the possible decodings and return the result
    dp[s] = tc
    return dp[s]
 
def CountWays(str):
 
    n = len(str)
 
    # empty string can form 1 valid decoding
    if(n == 0):
        return 1
 
    # dp vector to store the  number of ways
    # to decode each and every substring
    dp = [-1]*(n)
 
    # return the result
    return decodeMessage(dp, 0, str, n)
   
# driver code
if __name__ == "__main__" :
 
   str = "1234"
   print(CountWays(str))
 
  # This code is contributed by shinjanpatra.

C#

// C# program to implement
// the above approach
using System;
 
class GFG
{
 
  static int mod = 1000000007;
 
  // function which returns the number of ways to decode the message
  static int decodeMessage(int[] dp, int s, string str, int n)
  {
 
    // an empty string can also form 1 valid decoding
    if(s >= n)
      return 1;
 
    /*
        if we have already computed the number of
        ways to decode the substring return the
        answer directly
    */
    if(dp[s] != -1)
      return dp[s];
 
    int num,tc;
    num = tc = 0;
    for(int i=s;i<n;i++)
    {
      // generate the number
      num = num*10 + ((int)str[i] - '0');
 
      // validate the number
      if(num >= 1 && num <= 26)
      {
        /*
                since the number of ways to decode any string
                depends on the result of
                how the remaining string is decoded so get the
                number of ways how the rest of the string can
                be decoded
            */
        int c = decodeMessage(dp, i + 1, str, n);
 
        // add all the ways that the substring
        // from the current index can be decoded
        tc = (tc%mod + c%mod)%mod;
      }
 
      // leading 0’s or the number
      // generated so far is greater than 26
      // we can just stop the process
      // as it can never be a part of our solution
      else
        break;
    }
 
    // store all the possible decodings and return the result
    return (dp[s] = tc);
  }
  static int CountWays(string str)
  {
    int n = str.Length;
 
    // empty string can form 1 valid decoding
    if(n == 0)
      return 1;
 
    // dp vector to store the number of ways
    // to decode each and every substring
    int[] dp = new int[n];
    for(int i = 0; i < n; i++){
      dp[i] = -1;
    }
 
    // return the result
    return decodeMessage(dp,0,str,n);
  }
 
  // Driver Code
  public static void Main()
  {
    string str = "1234";
    Console.Write(CountWays(str));
  }
}
 
// This code is contributed by sanjoy_62.

Javascript

<script>
 
const mod = 1e9 + 7;
 
// function which returns the number of ways to decode the message
function decodeMessage(dp,s,str,n)
{
    // an empty string can also form 1 valid decoding
    if(s >= n)
        return 1;
     
    /*
        if we have already computed the number of
        ways to decode the substring return the
        answer directly
    */
    if(dp[s] != -1)
        return dp[s];
     
    let num,tc;
    num = tc = 0;
    for(let i=s;i<n;i++)
    {
        // generate the number
        num = num*10 + (str.charCodeAt(i) - '0'.charCodeAt(0));
 
        // validate the number
        if(num >= 1 && num <= 26)
        {
            /*
                since the number of ways to decode any string
                depends on the result of
                how the remaining string is decoded so get the
                number of ways how the rest of the string can
                be decoded
            */
            let c = decodeMessage(dp,i+1,str,n);
 
            // add all the ways that the substring
            // from the current index can be decoded
            tc = (tc%mod + c%mod)%mod;
        }
 
        // leading 0’s or the number
        // generated so far is greater than 26
        // we can just stop the process
        // as it can never be a part of our solution
        else
            break;
    }
 
    // store all the possible decodings and return the result
    return (dp[s] = tc);
}
function CountWays(str)
{
    let n = str.length;
 
    // empty string can form 1 valid decoding
    if(n == 0)
        return 1;
 
    // dp vector to store the  number of ways
    // to decode each and every substring
    let dp = new Array(n).fill(-1);
 
    // return the result
    return decodeMessage(dp,0,str,n);
}
// driver code
 
let str = "1234";
document.write(CountWays(str),"</br>");
 
// This code is contributed by shinjanpatra.
</script>
Output : 
3

Complejidad de tiempo:  O (N) donde N es la longitud de la string. Como estamos resolviendo todos y cada uno de los subproblemas solo una vez.

Complejidad espacial:   O (N) ya que estamos usando un vector para almacenar el resultado de todas y cada una de las substrings.

Publicación traducida automáticamente

Artículo escrito por GeeksforGeeks-1 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 *