For-loop DP solution in C; 0ms with comments


  • 0
    Z
    int numDecodings(char* s)
    {
      if(s==NULL || !strcmp(s,"")) return 0;
      
      int len = strlen(s);
      int dp[len]; // dp[i] means # of ways to decode upto s[i];
      if(s[0] > '0')  dp[0] = 1; // first char, one way if not leading 0
      else            return 0;
    
      for(int i = 1; i < len; i++)
      {
        // wrong encoding
        if(s[i] == '0' && (s[i-1] != '1' && s[i-1] !='2'))    return 0;
    
        //ambiguous cases
        if( ( (s[i-1] == '1') &&
              (s[i] > '0') && ( (i==len-1) || (s[i+1]!='0')))
            ||
            ( (s[i-1]=='2') &&
              ( ('1' <= s[i]) && (s[i] <= '6'))))
        {
          if(i>1)  dp[i] = dp[i-2] + dp[i-1];
          else     dp[i] = dp[i-1] +1;
    
          continue;
        }
        
        // no ambiguous for other cases
        dp[i] = dp[i-1]; 
      }
    
      return dp[len-1];
    }

Log in to reply
 

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