Find number of ways a string can be decoded into, if A=1, B=2, C=3 … Z=25 and encoding number is 123 ways decoding can be done is
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 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