Thought:
From the end to the front, use result[i - 2] & result[i - 1] to get the result[i].
Code:
public class Solution {
public int numDecodings(String s)
{
int len = s.length();
if(len == 0) return 0;
int[] result = new int[len+1];
result[len] = 1;
for(int i = len - 1; i >= 0; i--) {
if(s.charAt(i)!='0')
{
result[i] = result[i + 1];
if(i < len - 1 && Integer.parseInt(s.substring(i, i + 2)) <= 26)
result[i] += result[i+2];
}
}
return result[0];
}
}
public class Solution {
public int numDecodings(String s) {
if (s.length() == 0) return 0;
int[] result = new int[s.length() + 2];
result[1] = 1;
for (int i = 2; i < result.length; i++) {
char a = '1';
if (i >= 3) a = s.charAt(i - 3);
char b = s.charAt(i - 2);
if (b != '0') result[i] += result[i - 1];
if (a == '1' || a == '2' && b <= '6') result[i] += result[i - 2];
}
return result[result.length - 1];
}
}
No comments:
Post a Comment