Count possible decoding of a given digit sequence with hidden characters | Python program for the above approach ; check the first character of the string if it is ' * ' then 9 ways ; traverse the string ; 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 ; taking the value from previous step ; If previous character is 1 then the i - 1 th character and ith character can be decoded in a single character therefore , adding dp [ i - 1 ] . ; If previous character is 2 and ith character is less than 6 then the i - 1 th character and ith character can be decoded in a single character therefore , adding dp [ i - 1 ] . ; If previous character is * then it will contain the above 2 cases ; Driver code
M = 1000000007 NEW_LINE def waysOfDecoding ( s ) : NEW_LINE INDENT dp = [ 0 ] * ( len ( s ) + 1 ) NEW_LINE dp [ 0 ] = 1 NEW_LINE if s [ 0 ] == ' * ' : NEW_LINE INDENT dp [ 1 ] = 9 NEW_LINE DEDENT elif s [ 0 ] == '0' : NEW_LINE INDENT dp [ 1 ] = 0 NEW_LINE DEDENT else : NEW_LINE INDENT dp [ 1 ] = 1 NEW_LINE DEDENT for i in range ( len ( s ) ) : NEW_LINE INDENT if ( s [ i ] == ' * ' ) : NEW_LINE INDENT dp [ i + 1 ] = 9 * dp [ i ] NEW_LINE if ( s [ i - 1 ] == '1' ) : NEW_LINE INDENT dp [ i + 1 ] = ( dp [ i + 1 ] + 9 * dp [ i - 1 ] ) % M NEW_LINE DEDENT elif ( s [ i - 1 ] == '2' ) : NEW_LINE INDENT dp [ i + 1 ] = ( dp [ i + 1 ] + 6 * dp [ i - 1 ] ) % M NEW_LINE DEDENT elif ( s [ i - 1 ] == ' * ' ) : NEW_LINE INDENT dp [ i + 1 ] = ( dp [ i + 1 ] + 15 * dp [ i - 1 ] ) % M NEW_LINE DEDENT DEDENT else : NEW_LINE INDENT if s [ i ] != '0' : NEW_LINE INDENT dp [ i + 1 ] = dp [ i ] NEW_LINE DEDENT else : NEW_LINE INDENT dp [ i + 1 ] = 0 NEW_LINE DEDENT if ( s [ i - 1 ] == '1' ) : NEW_LINE INDENT dp [ i + 1 ] = ( dp [ i + 1 ] + dp [ i - 1 ] ) % M NEW_LINE DEDENT elif ( s [ i - 1 ] == '2' and s [ i ] <= '6' ) : NEW_LINE INDENT dp [ i + 1 ] = ( dp [ i + 1 ] + dp [ i - 1 ] ) % M NEW_LINE DEDENT elif ( s [ i - 1 ] == ' * ' ) : NEW_LINE INDENT if ( s [ i ] <= '6' ) : NEW_LINE INDENT dp [ i + 1 ] = dp [ i + 1 ] + 2 * dp [ i - 1 ] NEW_LINE DEDENT else : NEW_LINE INDENT dp [ i + 1 ] = dp [ i + 1 ] + 1 * dp [ i - 1 ] NEW_LINE DEDENT dp [ i + 1 ] = dp [ i + 1 ] % M NEW_LINE DEDENT DEDENT DEDENT return dp [ len ( s ) ] NEW_LINE DEDENT if __name__ == " _ _ main _ _ " : NEW_LINE INDENT s = "12" NEW_LINE print ( waysOfDecoding ( s ) ) NEW_LINE DEDENT