public int numDecodings(String s) {
int n1 =1, n2=1, n3=0;
if(s.length()==0s.charAt(0)=='0') return 0;
for(int i=2; i<=s.length(); i++)
{
n3=0;
if(s.charAt(i1)!='0') n3=n2;
int num = Integer.parseInt(s.substring(i2,i));
if(num>=10 && num<=26) n3+=n1;
n1=n2;
n2=n3;
}
return n2;
}
Simple java solution with O(1) space

@yanggao
If all of two adjacent digits in input are valid for a letter, it will be same as Fibonacci problem.
Example: input is "11111". Result is equal to "1111" plus "111".Here is my Java code with comments. It may help you to understand it:
public int numDecodings(String s) { if (s == null  s.length() == 0  s.startsWith("0")  s.matches(".*[^12]0.*")) return 0; int previousResult = 1; int result = 1; for (int i = 1; i < s.length(); i++) { int newResult; if (s.charAt(i) == '0') { // the last two digits must be converted together newResult = previousResult; } else if (s.charAt(i  1) != '0' && Integer.parseInt(s.substring(i  1, i + 1)) <= 26) { // the last two digits may or may not be converted together newResult = previousResult + result; } else { // the last two digits cannot be converted together newResult = result; } previousResult = result; result = newResult; } return result; }

@Mark_89 Brief but brilliant explanation for Fibonacci! And the regulation expression wowed me... Thanks!