Count Possible Decodings of a given Digit Sequence in O ( N ) time and Constant Auxiliary space | C ++ implementation to count decodings ; 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 bool to int ; Return the required answer ; Driver Code ; Function call
#include <bits/stdc++.h> NEW_LINE using namespace std ; int countDecodingDP ( string digits , int n ) { if ( digits [ 0 ] == '0' ) return 0 ; int count0 = 1 , count1 = 1 , count2 ; for ( int i = 2 ; i <= n ; i ++ ) { count2 = ( ( int ) ( digits [ i - 1 ] != '0' ) * count1 ) + ( int ) ( ( digits [ i - 2 ] == '1' ) or ( digits [ i - 2 ] == '2' and digits [ i - 1 ] < '7' ) ) * count0 ; count0 = count1 ; count1 = count2 ; } return count1 ; } int main ( ) { string digits = "1234" ; int n = digits . size ( ) ; cout << countDecodingDP ( digits , n ) ; return 0 ; }