Count Possible Decodings of a given Digit Sequence in O ( N ) time and Constant Auxiliary space | A Dynamic programming based function to count decodings in digit sequence ; For base condition "01123" should return 0 ; Using last two calculated values , calculate for ith index ; Change boolean to int ; Return the required answer ; Driver Code ; Function call
def countDecodingDP ( digits , n ) : NEW_LINE INDENT if ( digits [ 0 ] == '0' ) : NEW_LINE INDENT return 0 ; NEW_LINE DEDENT count0 = 1 ; count1 = 1 ; NEW_LINE for i in range ( 2 , n + 1 ) : NEW_LINE INDENT dig1 = 0 ; dig3 = 0 ; NEW_LINE if ( digits [ i - 1 ] != '0' ) : NEW_LINE INDENT dig1 = 1 ; NEW_LINE DEDENT if ( digits [ i - 2 ] == '1' ) : NEW_LINE INDENT dig2 = 1 ; NEW_LINE DEDENT else : NEW_LINE INDENT dig2 = 0 ; NEW_LINE DEDENT if ( digits [ i - 2 ] == '2' and digits [ i - 1 ] < '7' ) : NEW_LINE INDENT dig3 = 1 ; NEW_LINE DEDENT count2 = dig1 * count1 + NEW_LINE INDENT dig2 + dig3 * count0 ; NEW_LINE DEDENT count0 = count1 ; NEW_LINE count1 = count2 ; NEW_LINE DEDENT return count1 ; NEW_LINE DEDENT if __name__ == ' _ _ main _ _ ' : NEW_LINE INDENT digits = "1234" ; NEW_LINE n = len ( digits ) ; NEW_LINE print ( countDecodingDP ( digits , n ) ) ; NEW_LINE DEDENT