1ms java clean solution with explanation


  • 0
    Q
    1. numbers that starts with 1,2 may have two ways of decoding. Decode by single '1'('2') or decode with the following number togeter, Therefore, if current element is i, f(i) = f(i + 1) + f(i + 2)(note that the second part may not exist when the ith elememnt is 2 and the (i + 1)th element is greater than 6).
    2. numbers that starts with 0 cannot be decoded.

    public int numDecodings(String s) {
        int n = s.length();
        char[] c = s.toCharArray();
        if ((n == 0) || (c[0] == '0')) return 0;
        if (n == 1) return 1;
        int f2 = c[n - 1] == '0' ? 0 : 1; // f(i + 2), start from c[n - 1]
        int f1 = c[n - 2] == '0' ? 0 : f2; // f(i + 1), start from c[n - 2]
        if ((c[n - 2] == '1') || ((c[n - 2] == '2') && (c[n - 1] < '7'))) f1++;  
        for (int i = n - 3; i >= 0; i--){
            if (c[i] == '0'){
                if ((c[i - 1] != '1') && (c[i - 1] != '2')) return 0; //unable to decode 0
                else {
                    i--;
                    f2 = 0; //f1 maintains the same
                    continue;
                }
            } 
            if ((c[i] != '1') && ((c[i] != '2') || (c[i + 1] > '6'))) f2 = f1; //f1 maintains the same
            else {
                int t = f1;
                f1 = f1 + f2;
                f2 = t;
            }
        }
        return f1;
    }

Log in to reply
 

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