# Simple java solution with O(1) space

• ``````public int numDecodings(String s) {
int n1 =1, n2=1, n3=0;
if(s.length()==0||s.charAt(0)=='0') return 0;
for(int i=2; i<=s.length(); i++)
{
n3=0;
if(s.charAt(i-1)!='0') n3=n2;
int num = Integer.parseInt(s.substring(i-2,i));
if(num>=10 && num<=26) n3+=n1;
n1=n2;
n2=n3;
}
return n2;
}``````

• hi lmx707, could you explain it? esp. what is the meaning of n1, n2 and n3?

• looks like fibonacci, but i am not sure how it relates to fibonacci...

• @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".

``````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!

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.