Count possible decodings of a given Digit Sequence | Set 2 | C ++ implementation to count the possible decodings of the given digit sequence ; Function to count the number of ways to decode the given digit sequence ; Array to store the dp states ; Case of empty string ; Condition to check if the first character of string is 0 ; Base case for single length string ; Bottom - up dp for the string ; Previous character ; Current character ; Case to include the Current digit as a single digit for decoding the string ; Case to include the current character as two - digit for decoding the string ; Condition to check if the current character is " * " ; Condition to check if the current character is less than or equal to 26 ; Condition to check if the Previous digit is equal to " * " ; Driver Code ; Function Call
#include <bits/stdc++.h> NEW_LINE using namespace std ; int waysToDecode2 ( string s ) { int n = s . size ( ) ; vector < int > dp ( n + 1 , 0 ) ; dp [ 0 ] = 1 ; if ( s [ 0 ] == '0' ) return 0 ; dp [ 1 ] = ( ( s [ 0 ] == ' * ' ) ? 9 : 1 ) ; for ( int i = 2 ; i <= n ; i ++ ) { char first = s [ i - 2 ] ; char second = s [ i - 1 ] ; if ( second == ' * ' ) { dp [ i ] += 9 * dp [ i - 1 ] ; } else if ( second > '0' ) dp [ i ] += dp [ i - 1 ] ; if ( first == '1' first == '2' ) { if ( second == ' * ' ) { if ( first == '1' ) dp [ i ] += 9 * dp [ i - 2 ] ; else if ( first == '2' ) dp [ i ] += 6 * dp [ i - 2 ] ; } else if ( ( ( first - '0' ) * 10 + ( second - '0' ) ) <= 26 ) dp [ i ] += dp [ i - 2 ] ; } else if ( first == ' * ' ) { if ( second == ' * ' ) { dp [ i ] += 15 * dp [ i - 2 ] ; } else if ( second <= '6' ) dp [ i ] += 2 * dp [ i - 2 ] ; else dp [ i ] += dp [ i - 2 ] ; } } return dp [ n ] ; } int main ( ) { string str = "12*3" ; cout << waysToDecode2 ( str ) << endl ; return 0 ; }