leetcode

Solution to some Leetcode problems written in C++
git clone git://git.dimitrijedobrota.com/leetcode.git
Log | Files | Refs | README | LICENSE

1416.cpp (627B)

      1 class Solution {
      2     static const int mod = 1E9 + 7;
      3     static const int size = 1E5 + 1;
      4     int dp[size];
      5 
      6   public:
      7     Solution() { memset(dp, 0xFF, sizeof(dp)); }
      8 
      9     int numberOfArrays(const string &s, int k, int crnt = 0) {
     10         if (crnt >= s.size()) return 1;
     11         if (s[crnt] == '0') return 0;
     12         if (dp[crnt] != -1) return dp[crnt];
     13 
     14         long long num = 0, res = 0;
     15         for (int i = crnt; i < s.size(); i++) {
     16             num = num * 10 + (s[i] - '0');
     17             if (num > k) break;
     18             res = (res + numberOfArrays(s, k, i + 1)) % mod;
     19         }
     20 
     21         return dp[crnt] = res;
     22     }
     23 };