leetcode

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

1531.cpp (855B)

      1 class Solution {
      2     static int dp[127][127];
      3 
      4     static int digits(int x) {
      5         if (x == 1) return 0;
      6         if (x < 10) return 1;
      7         if (x < 100) return 2;
      8         return 3;
      9     }
     10 
     11   public:
     12     Solution() { memset(dp, 0xFF, sizeof(dp)); }
     13     int getLengthOfOptimalCompression(const string &s, int k, int crnt = 0) const {
     14         const int n = s.size();
     15         if (k < 0) return n;
     16         if (crnt >= n || n - crnt <= k) return 0;
     17         if (dp[crnt][k] != -1) return dp[crnt][k];
     18         int res = n, cnt[27] = {0};
     19         for (int j = crnt, maxi = 0; j < n; j++) {
     20             maxi = max(maxi, ++cnt[s[j] & 0x1F]);
     21             res = min(res,
     22                       1 + digits(maxi) + getLengthOfOptimalCompression(s, k - (j - crnt + 1 - maxi), j + 1));
     23         }
     24         return dp[crnt][k] = res;
     25     }
     26 };
     27 
     28 int Solution::dp[127][127];