[How to from Error to AC ]thoughts with C++ implementation


  • 2

    As other problem, there are also some traps and corner cases which make me not AC for one time.

    The recursion is a bit easy. But need to consider when to use one char , we should check whether it

    equals '0', then it does not equal to '0'. We should check whether the 2-char-composed-string is valid.

    And the dp[0] equal to 1 for the purpose of the DP idea.

    All in all , there are the AC implementation.

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

  • 0
    2
            dp[i] = dp[i-1] + ((s[i-2] == '1' || (s[i-2] == '2' && s[i-1] <= '6')) ? dp[i-2] : 0);
    

    is diiferent from

          dp[i] = dp[i-1] + (s[i-2] == '1' || (s[i-2] == '2' && s[i-1] <= '6')) ? dp[i-2] : 0;
    

    The second case will frist add the dp[i-1] and all the stuff before '?'..........


Log in to reply
 

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