Saturday, March 2, 2013

[LeetCode] Decode Ways

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