Straightforward C++ solution


  • 1
    S
    //if hasError(s[i-1],s[i]), we never get a correct decoding way, return 0;   
    bool hasError(char a, char b)
    { return (a=='0'&&b=='0') || (a>'2'&&b=='0'); }
    
    //if s[i-1] and s[i] must be connected, f[i] = f[i-2];
    bool mustConnect(char a, char b)
    { return b == '0'; }
    
    //if s[i-1] and s[i] must be separated, f[i] = f[i-1];
    bool mustDecode(char a, char b)
    { return a>'2'||a=='0'||(a=='2'&&b>'6'); }
    
    int numDecodings(string s) 
    {
    	if(s.empty()||'0'==s[0]) return 0;
    	vector<int> f(s.size(),0);
    	f[0] = 1;
    	for(int i=1; i!=s.size(); ++i)
    	{
    		if(hasError(s[i-1],s[i])) return 0;
    		else if(mustDecode(s[i-1],s[i])) f[i] = f[i-1];
    		else if(mustConnect(s[i-1],s[i])) f[i] = i==1 ? 1:f[i-2];
    		else f[i] = i==1 ? 2 : f[i-1]+f[i-2];
    	}
    	return f[s.size()-1];
    }

  • 0
    L

    Can you add comments to explain?


Log in to reply
 

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