text: Count possible decoding of a given digit sequence with hidden characters | C ++ program for the above approach ; If s [ i ] = = ' * ' there can be 9 possible values of * ; 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 previous character is 2 then the words that can be formed are U ( 21 ) , V ( 22 ) , W ( 23 ) , X ( 24 ) Y ( 25 ) , Z ( 26 ) ; If the previous digit is * then all 15 2 - digit characters can be formed ; If s [ i ] != ' * ' ; Adding first in second if s [ i - 1 ] = 1 ; Adding first in second if s [ i - 1 ] = = 2 and s [ i ] <= '6' ; If s [ i - 1 ] = = ' * ' the union of above 2 cases has to be done ; Driver code
code: #include <bits/stdc++.h> NEW_LINE 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 ] == ' * ' ) { second = 9 * second ; if ( s [ i - 1 ] == '1' ) second = ( second + 9 * first ) % M ; else if ( s [ i - 1 ] == '2' ) second = ( second + 6 * first ) % M ; else if ( s [ i - 1 ] == ' * ' ) second = ( second + 15 * first ) % M ; } else { second = s [ i ] != '0' ? second : 0 ; if ( s [ i - 1 ] == '1' ) second = ( second + first ) % M ; else if ( s [ i - 1 ] == '2' && s [ i ] <= '6' ) second = ( second + first ) % M ; else if ( s [ i - 1 ] == ' * ' ) second = ( second + ( s [ i ] <= '6' ? 2 : 1 ) * first ) % M ; } first = temp ; } return ( int ) second ; } int main ( ) { string s = " * " ; cout << waysOfDecoding ( s ) ; return 0 ; }