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
using System ; class GFG { static 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 ++ ) { int dig1 = 0 , dig2 , dig3 = 0 ; if ( digits [ i - 1 ] != '0' ) { dig1 = 1 ; } if ( digits [ i - 2 ] == '1' ) { dig2 = 1 ; } else dig2 = 0 ; if ( digits [ i - 2 ] == '2' && digits [ i - 1 ] < '7' ) { dig3 = 1 ; } count2 = dig1 * count1 + dig2 + dig3 * count0 ; count0 = count1 ; count1 = count2 ; } return count1 ; } public static void Main ( String [ ] args ) { String digits = "1234" ; int n = digits . Length ; Console . Write ( countDecodingDP ( digits , n ) ) ; } }