1 2 3 = A B C

1 23 = A X

12 3 = L C

How to find total number of decodings possible.

this is DP problem.

Start thinking in pattern.if

1 2 3 is String/Array input.

– 1 can be decoded in 1 way.

– 2 cab be decoded in 1 way.

– 1 2 (along with previous one < 26) so 2 can be decoded in (old number of way + 1) = 2 ways

– 3 can be decoded in 1 way

– 2 3 ( can be decoded also as < 26) so total = 3 ways.

Total ways = 3

Algo

input

string A[N]

NoOfWay[0]=1

NoOfWay[1]=2

for (i=1 to N){

if (A[i] <= 26) NoOfWay [ i+1 ] = NoOfWay [ i ];

if ( A[i] + (A[i-1]*10) <= 26 ) NoOfWay [ i+1 ] = NoOfWay [ i+1 ] + NoOfWay [ i – 1 ];

}

return NoOfWay [ N ]

Its very easy to code.

You can try ur self.

PS : We have assumed that number will be in range of 1-9.

You can edit algo/code to ensure numbers like 103 also. (0-9)

You can working code : http://ideone.com/2QA9Cq