C++, 5ms, O(n) time and O(1) space, without DP, hashtable, recursive


  • 1
    S
    class Solution {
    public:
        // Here is a straightforward method.
        // Define res(n) as the total number of ways to decode string(n) 
        // which is a string of length n. When the next char of string(n) 
        // can be decoded two times, for example: 
        //     the next char: 2
        //     the last char of string(n): 1
        // res(n + 1) will be res(n) + res(n - 1).
        // If not, for example:
        //     the next char: 8
        //     the last char of string(n): 2 ~ 9
        // res(n + 1) simply equal res(n).
        // Special case:
        //     Zero, 0. When the next char of string(n) is 0 and res(n) > res(n - 1), 
        //     which means two-times decoding occurs at string(n), the 
        //     two-times decoding has to be reverted.
        //     res(n + 1) = res(n - 1)
        int numDecodings(string s) {
            if (s.length() == 0 || s[0] == '0') {
                return 0;
            }
            int res, pre, ppre;
            res = ppre = pre = 1;
            for (int i = 1; i < s.length(); i ++) {
                if (s[i] == '0') {
                    if (s[i - 1] != '1' && s[i - 1] != '2') {
                        return 0;   
                    } else if (pre > ppre) {
                        res = ppre;
                        pre = res;
                    } else {
                        ppre = pre;
                    }
                } else {
                    if ((s[i - 1] == '1') || (s[i - 1] == '2' && s[i] <= '6')) {
                        res = ppre + pre;
                        ppre = pre;
                        pre = res;
                    } else {
                        ppre = pre;
                    }
                }
            }
            return res;
        }
    };

  • 0
    I

    Here is a Java version...

    public class Solution {
        public int numDecodings(String s) {
            if(s==null||s.length()==0 || s.charAt(0)=='0'){
                return 0;
            }
            if(s.length()==1){
                return 1;
            }
            int pre=1, ppre=1, res=1;
            for(int i=1;i<s.length();i++){
                if(s.charAt(i)=='0'){
                    if(s.charAt(i-1)!='1' && s.charAt(i-1)!='2'){
                        return 0;
                    }else if(pre > ppre){
                        res = ppre;
                        pre = res;
                    }else{
                        ppre = pre;
                    }
                }else{
                    if(s.charAt(i-1)=='1'||(s.charAt(i-1)=='2'&&s.charAt(i)<='6')){
                        res = pre + ppre;
                        ppre = pre;
                        pre = res;
                    }else{
                        ppre = pre;
                    }
                }
            }
            return res;
        }
    }

Log in to reply
 

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