A concise dp solution


  • 110
    S
    int numDecodings(string s) {
        if (!s.size() || s.front() == '0') return 0;
        // r2: decode ways of s[i-2] , r1: decode ways of s[i-1] 
        int r1 = 1, r2 = 1;
        
        for (int i = 1; i < s.size(); i++) {
            // zero voids ways of the last because zero cannot be used separately
            if (s[i] == '0') r1 = 0;
    
            // possible two-digit letter, so new r1 is sum of both while new r2 is the old r1
            if (s[i - 1] == '1' || s[i - 1] == '2' && s[i] <= '6') {
                r1 = r2 + r1;
                r2 = r1 - r2;
            }
    
            // one-digit letter, no new way added
            else {
                r2 = r1;
            }
        }
    
        return r1;
    }

  • 2
    L

    I have a question. The index of the string is from left to right, but the number sorting (units, tens, hundreds ...) is from right to left. Why the DP from left to right is still working ? (shouldn't we start from right to left?)
    Thanks.


  • 0
    N

    I think the author use units to do some check, so it never minds the direction.s[i - 1] == '1' || s[i - 1] == '2' && s[i] <= '6'


  • -9
    E
     if (s[i] == '0') r1 = 0;
    

    I tried your code under test case s = "201", the correct answer should be one, but I got zero.

    I think if you wanna avoid these complicated '0' cases, the only way is to visit the string from back to end, like the code below.

    Otherwise, you need to consider two kinds of cases, one is like "120" which is valid, and the other one is "130" which returns zero immediately.

    int numDecodings(string s) {
    	int len = s.size();
    	if(!len) return 0; 
    
    	vector<int> memo(len+1, 0);
    	memo[len] = 1; 
    	memo[len-1] = s[len-1] == '0' ? 0 : 1;
    	
    	for (int i = len-2; i >= 0; --i)
    	{
    		if(s[i] == '0') continue; 
    		else{
    			if(stoi(s.substr(i,2))<=26)
    				memo[i] = memo[i+1]+memo[i+2];
    			else memo[i] = memo[i+1];
    
    		}
    	}
    
    	return memo[0]; 
        
    }

  • 0
    Y

    shichaotan's code runs correctly under case s = "201".


  • 1
    R

    We thought exactly the same way~~ lol

        public class Solution {
        public int numDecodings(String s) {
            
            if (s.length() == 0) return 0;
            int dpn_2 = 1;
            int dpn_1 = 0;
            if(s.charAt(0)=='0') return 0;
            else dpn_1 =1;
            
            for(int i=1;i
                int dpn=0;
                if(s.charAt(i)=='0'){
                    dpn_1=0;
                }
                dpn=(Integer.parseInt(s.substring(i-1,i+1))<=26)?dpn_1+dpn_2:dpn_1;
                dpn_2=dpn_1;
                dpn_1=dpn;
            }
            
            return dpn_1;
        }
    }
    

  • 1
    Q

    Really elegant implementation of the general Fibonacci Numbers.
    The DP use the least space. I think it would be better to add the exit if (s.charAt(i - 1) == 0) return 0; in the first if.

    Thanks for sharing.


  • 0
    S

    This is brilliant!


  • 0

    Good solution.


  • 0
    D

    his code has "if,if,else" ,not "if,else if, else"


  • 0
    H

    // r2: decode ways of s[i-2] , r1: decode ways of s[i-1]
    int r1 = 1, r2 = 1;

    I have a question for the initial value r1 and r2, why both of them are assigned to 1? I am curious the meanings behind this initial value. I can understand the first entry into for loop is i==1, so r1 is the way of decoding for s[0], and it is not '0', so the initial value should be 1. How to explain the r2 which is s[-1]? Anyone? Thanks.


  • 0

    You can take "12" as a startup initialisation instead of [-1, 0] for r2 and r1 respectively


  • 0
    S
    class Solution {
    public:
        int numDecodings(string s) {
            int n = s.size();
            if(n==0 || s[0]=='0') return 0;
            vector<int> f(n+1,1);
            for(int i=2;i<=n;i++)
            {
                if(s[i-1]=='0') f[i]=0;
                else f[i] = f[i-1];
                if(s[i-2]=='1' || s[i-2]=='2' && s[i-1]<='6')
                    f[i] += f[i-2];
            }
            return f[n];
        }
    };

  • 0
    T

    can anybody explain initial values of r1 and r2. Why they both are 1 ?

    // r2: decode ways of s[i-2] , r1: decode ways of s[i-1]
    int r1 = 1, r2 = 1;


Log in to reply
 

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