A message containing letters from
A-Z
is being encoded to numbers using the following mapping:'A' -> 1
'B' -> 2
...
'Z' -> 26
Given an encoded message containing digits, determine the total number of ways to decode it.
For example,
Given encoded message
"12"
, it could be decoded as "AB"
(1 2) or "L"
(12).
The number of ways decoding
"12"
is 2.Solution:
Notice that the number of ways of decoding a string till the ith character is the number of ways of deciding till the previous one (if the ith character is not '0') plus the number of ways to decode till two before (if the last two characters make a valid letter coding, i.e. from 10 till 26).public class Solution { public int numDecodings(String s) { if(s.length()==0) return 0; int previous = 0; int actual = 1; for(int i=0; i<s.length(); i++) { if(!Character.isDigit(s.charAt(i))) return 0; int temp = s.charAt(i) != '0' ? actual : 0; if(i>0 && s.charAt(i-1)!='0' && Integer.parseInt(s.substring(i-1,i+1))<27) temp += previous; previous= actual; actual = temp; } return actual; } }
No comments :
Post a Comment