Рубрики

Подсчет возможных расшифровок заданной последовательности цифр

Пусть 1 представляет «A», 2 представляет «B» и т. Д. Учитывая последовательность цифр, подсчитайте количество возможных декодирований данной последовательности цифр.

Примеры:

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

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

Считается, что пустая последовательность цифр имеет одно декодирование. Можно предположить, что входные данные содержат действительные цифры от 0 до 9, и нет начальных 0, никаких дополнительных конечных 0 и двух или более последовательных 0.

Эта проблема рекурсивна и может быть разбита на подзадачи. Мы начинаем с конца данной последовательности цифр. Мы инициализируем общее количество декодирований как 0. Мы повторяем для двух подзадач.
1) Если последняя цифра отлична от нуля, повторите оставшиеся (n-1) цифры и добавьте результат к общему количеству.
2) Если последние две цифры образуют действительный символ (или меньше 27), повторить оставшиеся (n-2) цифры и добавить результат к общему количеству.

Ниже приводится реализация вышеуказанного подхода.

C ++

// Наивная рекурсивная реализация C ++ для подсчета количества декодирований
// который может быть сформирован из заданной последовательности цифр
#include <iostream>
#include <cstring>

using namespace std;

  
// Задана последовательность цифр длиной n,
// возвращает количество возможных расшифровок
// замена 1 на A, 2 на B, ... 26 на Z

int countDecoding(char *digits, int n)

{

    // базовые случаи

    if (n == 0 || n == 1)

        return 1;

    if(digits[0]=='0')

          return 0;

    // для базового условия "01123" должен возвращать 0

    int count = 0;  // Инициализировать счет

  

    // Если последняя цифра не равна 0,

    // тогда последняя цифра должна добавить к числу слов

    if (digits[n-1] > '0')

        count =  countDecoding(digits, n-1);

  

    // Если две последние цифры образуют число меньше

    // чем или равно 26, то рассмотрим

    // последние две цифры и повторяем

    if (digits[n-2] == '1' || 

                  (digits[n-2] == '2' && digits[n-1] < '7') )

        count +=  countDecoding(digits, n-2);

  

    return count;

}

  
// Программа драйвера для проверки вышеуказанной функции

int main()

{

    char digits[] = "1234";

    int n = strlen(digits);

    cout << "Count is " << countDecoding(digits, n);

    return 0;

}
// Изменено Атану Сеном

Джава

// Наивная рекурсивная реализация Java
// посчитать количество расшифровок, которые
// может быть сформирован из заданной последовательности цифр

  

class GFG {

      
// Задана последовательность цифр длиной n,
// возвращает количество возможных расшифровок
// замена 1 на A, 2 на B, ... 26 на Z

static int countDecoding(char[] digits, int n) 

{

    // базовые случаи

    if (n == 0 || n == 1)

    return 1;

    if(digits[0]=='0')   // для базового условия "01123" должен возвращать 0

          return 0;

  

    // Инициализировать счет

    int count = 0

  

    // Если последняя цифра не равна 0, то

    // последняя цифра должна добавить к

    // количество слов

    if (digits[n - 1] > '0')

    count = countDecoding(digits, n - 1);

  

    // Если две последние цифры образуют число

    // меньше или равно 26,

    // затем рассмотрим две последние цифры и повторим

    if (digits[n - 2] == '1' || 

       (digits[n - 2] == '2' && digits[n - 1] < '7'))

    count += countDecoding(digits, n - 2);

  

    return count;

}

  
// Программа драйвера для проверки вышеуказанной функции

public static void main(String[] args) 

{

    char digits[] = {'1', '2', '3', '4'};

    int n = digits.length;

    System.out.printf("Count is %d", countDecoding(digits, n));

}
}

  
// Этот код предоставлен Смитой Динеш Семвал.
// Изменено Атану Сеном

python3

# Динамическое программирование на основе
# Реализация Python3 для подсчета декодирований

  
# Динамическое программирование на основе
# функция для подсчета декодирований

def countDecodingDP(digits, n):

          

        # Таблица для хранения результатов подзадач

    count = [0] * (n+1

    count[0] = 1

    count[1] = 1

  

    for i in range(2, n+1):

      

        count[i] = 0

  

        # Если последняя цифра не равна 0,

                # тогда последняя цифра должна добавить к

        # количество слов

        if (digits[i-1] > '0'):

            count[i] = count[i-1]

  

        # Если вторая последняя цифра меньше

                № 2 и последняя цифра

        # меньше 7, затем два последних

                # цифры образуют действительный символ

        if (digits[i-2] == '1' or (digits[i-2] == '2' and digits[i-1] < '7') ):

            count[i] += count[i-2]

      

    return count[n]

  

  
# Программа драйвера для проверки вышеуказанной функции

digits = ['1','2','3','4']

n = len(digits)

  

print("Count is ",countDecodingDP(digits, n))

  
# Этот код предоставлен
# Смита Динеш Семвал

C #

// Наивная рекурсивная реализация C #
// посчитать количество расшифровок, которые
// может быть сформирован из заданной последовательности цифр

using System;

  

class GFG {

      

    // Задана последовательность цифр длиной n,

    // возвращает количество возможных расшифровок

    // заменяя 1 на A, 2 на B, ...

    // 26 с Z

    static int countDecoding(char []digits, int n) 

    {

          

        // базовые случаи

        if (n == 0 || n == 1)

        return 1;

      

        // Инициализировать счет

        int count = 0; 

      

        // Если последняя цифра не равна 0, то

        // последняя цифра должна добавить к

        // количество слов

        if (digits[n - 1] > '0')

        count = countDecoding(digits, n - 1);

      

        // Если две последние цифры образуют число

        // меньше или равно 26, тогда

        // рассмотреть две последние цифры и повторить

        if (digits[n - 2] == '1' || 

                    (digits[n - 2] == '2' && 

                       digits[n - 1] < '7'))

            count += countDecoding(digits, n - 2);

      

        return count;

    }

      

    // Программа драйвера для проверки вышеуказанной функции

    public static void Main() 

    {

        char []digits = {'1', '2', '3', '4'};

        int n = digits.Length;

        Console.Write("Count is ");

        Console.Write(countDecoding(digits, n));

    }

}

  
// Этот код предоставлен нитин митталь.

PHP

<?php 
// Наивная рекурсивная реализация PHP
// посчитать количество расшифровок, которые могут
// формируется из заданной последовательности цифр

  
// Задана последовательность цифр длиной n,
// возвращает количество возможных расшифровок
// замена 1 на A, 2 на B, ... 26 на Z

function countDecoding(&$digits, $n)

{

    // базовые случаи

    if ($n == 0 || $n == 1)

        return 1;

  

    $count = 0; // Инициализировать счет

  

    // Если последняя цифра не равна 0, то последняя

    // цифра должна добавить к числу слов

    if ($digits[$n - 1] > '0')

        $count = countDecoding($digits, $n - 1);

  

    // Если две последние цифры образуют число

    // меньше или равно 26, тогда

    // рассмотреть две последние цифры и повторить

    if ($digits[$n - 2] == '1' || 

       ($digits[$n - 2] == '2' && 

        $digits[$n - 1] < '7') )

        $count += countDecoding($digits, $n - 2);

  

    return $count;

}

  
// Код драйвера

$digits = "1234";

$n = strlen($digits);

echo "Count is " . countDecoding($digits, $n);

  
// Этот код предоставлен ita_c
?>


Выход:

Count is 3

Временная сложность приведенного выше кода является экспоненциальной. Если мы поближе рассмотрим вышеупомянутую программу, то увидим, что рекурсивное решение аналогично числам Фибоначчи . Таким образом, мы можем оптимизировать вышеупомянутое решение для работы за O (n) время, используя динамическое программирование .
Ниже приводится реализация для того же.

C ++

// Динамическое программирование на C ++
// реализация для подсчета декодирований
#include <iostream>
#include <cstring>

using namespace std;

  
// Функция на основе динамического программирования
// посчитать декодирования

int countDecodingDP(char *digits, int n)

{

    // Таблица для хранения результатов подзадач

    int count[n+1]; 

    count[0] = 1;

    count[1] = 1;

    // для базового условия "01123" должен возвращать 0

    if(digits[0]=='0')  

         return 0;

    for (int i = 2; i <= n; i++)

    {

        count[i] = 0;

  

        // Если последняя цифра не равна 0,

        // тогда последняя цифра должна добавить к числу слов

        if (digits[i-1] > '0')

            count[i] = count[i-1];

  

        // Если вторая последняя цифра меньше

        // чем 2 и последняя цифра меньше 7,

        // тогда последние две цифры образуют действительный символ

        if (digits[i-2] == '1' || 

              (digits[i-2] == '2' && digits[i-1] < '7') )

            count[i] += count[i-2];

    }

    return count[n];

}

  
// Программа драйвера для проверки вышеуказанной функции

int main()

{

    char digits[] = "1234";

    int n = strlen(digits);

    cout << "Count is " << countDecodingDP(digits, n);

    return 0;

}
// Изменено Атану Сеном

Джава

// Динамическое программирование на основе Java
// реализация для подсчета декодирований

import java.io.*;

  

class GFG 

{

      
// Динамическое программирование на основе
// функция для подсчета декодирований

static int countDecodingDP(char digits[], 

                           int n)

{

    // Таблица для хранения результатов подзадач

    int count[] = new int[n + 1]; 

    count[0] = 1;

    count[1] = 1;

    if(digits[0]=='0')   // для базового условия "01123" должен возвращать 0

          return 0;

    for (int i = 2; i <= n; i++)

    {

        count[i] = 0;

  

        // Если последняя цифра не равна 0,

        // тогда последняя цифра должна добавить к

        // количество слов

        if (digits[i - 1] > '0')

            count[i] = count[i - 1];

  

        // Если вторая последняя цифра меньше

        // чем 2 и последняя цифра меньше

        // чем 7, то последние две цифры

        // сформировать действительный символ

        if (digits[i - 2] == '1' ||

           (digits[i - 2] == '2' && 

            digits[i - 1] < '7'))

            count[i] += count[i - 2];

    }

    return count[n];

}

  
// Код драйвера

public static void main (String[] args) 

{

    char digits[] = {'1','2','3','4'};

    int n = digits.length;

    System.out.println("Count is "

               countDecodingDP(digits, n));

}
}

  
// Этот код предоставлен anuj_67
// Изменено Атану Сеном

python3

# Динамическое программирование на основе Python3
# реализация для подсчета декодирований

  
# Функция на основе динамического программирования
# считать декодирования

def countDecodingDP(digits, n): 

  

    count = [0] * (n + 1); # Стол для хранения

                           # результаты подзадач

    count[0] = 1

    count[1] = 1

  

    for i in range(2, n + 1): 

  

        count[i] = 0

  

        # Если последняя цифра не равна 0, то последняя

        # цифра должна добавить к числу слов

        if (digits[i - 1] > '0'): 

            count[i] = count[i - 1]; 

  

        # Если вторая последняя цифра меньше 2

        # и последняя цифра меньше 7, тогда

        # последние две цифры образуют действительный символ

        if (digits[i - 2] == '1' or 

           (digits[i - 2] == '2' and 

            digits[i - 1] < '7') ): 

            count[i] += count[i - 2]; 

  

    return count[n]; 

  
Код водителя

digits = "1234"

n = len(digits); 

print("Count is"

       countDecodingDP(digits, n)); 

  
# Этот код предоставлен mits

C #

// Динамическое программирование на C #
// реализация для подсчета декодирований

using System;

  

class GFG 

{

      
// Динамическое программирование на основе
// функция для подсчета декодирований

static int countDecodingDP(char[] digits, 

                           int n)

{

    // Таблица для хранения результатов подзадач

    int[] count = new int[n + 1]; 

    count[0] = 1;

    count[1] = 1;

  

    for (int i = 2; i <= n; i++)

    {

        count[i] = 0;

  

        // Если последняя цифра не равна 0,

        // тогда последняя цифра должна добавить к

        // количество слов

        if (digits[i - 1] > '0')

            count[i] = count[i - 1];

  

        // Если вторая последняя цифра меньше

        // чем 2 и последняя цифра меньше

        // чем 7, то последние две цифры

        // сформировать действительный символ

        if (digits[i - 2] == '1' ||

           (digits[i - 2] == '2' && 

            digits[i - 1] < '7'))

            count[i] += count[i - 2];

    }

    return count[n];

}

  
// Код драйвера

public static void Main() 

{

    char[] digits = {'1','2','3','4'};

    int n = digits.Length;

    Console.WriteLine("Count is "

            countDecodingDP(digits, n));

}
}

  
// Этот код добавлен
// Аканкша Рай
// Изменено Атану Сеном

PHP

<?php
// Динамическое программирование на основе
// реализация php для подсчета декодирований

  
// Функция на основе динамического программирования для подсчета декодирования

function countDecodingDP($digits, $n

    // Таблица для хранения результатов подзадач

    $count[$n+1]=array(); 

    $count[0] = 1; 

    $count[1] = 1; 

  

    for ($i = 2; $i <= $n; $i++) 

    

        $count[$i] = 0; 

  

        // Если последняя цифра не равна 0, то последняя цифра должна быть добавлена к

        // количество слов

        if ($digits[$i-1] > '0'

            $count[$i] = $count[$i-1]; 

  

        // Если вторая последняя цифра меньше 2 и последняя цифра

        // меньше 7, тогда последние две цифры образуют действительный символ

        if ($digits[$i-2] == '1' || ($digits[$i-2] == '2' && $digits[$i-1] < '7') ) 

            $count[$i] += $count[$i-2]; 

    

    return $count[$n]; 

  
// Программа драйвера для проверки вышеуказанной функции

    $digits = "1234"

    $n = strlen($digits); 

    echo  "Count is " , countDecodingDP($digits, $n); 

  
#This code is contributed by ajit.
?>


Выход:

Count is 3

Сложность по времени вышеупомянутого решения составляет O (n) и требует O (n) вспомогательного пространства. Мы можем уменьшить вспомогательное пространство до O (1), используя оптимизированную для пространства версию, обсуждаемую в Посте числа Фибоначчи .

Пожалуйста, напишите комментарии, если вы обнаружите что-то неправильное, или вы хотите поделиться дополнительной информацией по обсуждаемой теме

Рекомендуемые посты:

Подсчет возможных расшифровок заданной последовательности цифр

0.00 (0%) 0 votes