leetcode

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

1255.cpp (1363B)

      1 class Solution {
      2     static int count[16][27];
      3     mutable array<int, 26> crnt{0};
      4 
      5     int rec(const int n, const int idx = 0, const int score = 0) const {
      6         if (idx == n) return score;
      7 
      8         int res = rec(n, idx + 1, score);
      9         auto back = crnt;
     10         for (int i = idx; i < n; i++) {
     11             bool valid = true;
     12             for (int j = 0; j < 26; j++) {
     13                 crnt[j] += count[i][j];
     14                 if (crnt[j] > count[n][j]) {
     15                     valid = false;
     16                     break;
     17                 }
     18             }
     19             if (valid) res = max(res, rec(n, i + 1, score + count[i][26]));
     20             crnt = back;
     21         }
     22 
     23         return res;
     24     }
     25 
     26   public:
     27     int maxScoreWords(const vector<string> &words, const vector<char> &letters,
     28                       const vector<int> &score) const {
     29         memset(count, 0x00, sizeof(count));
     30 
     31         const int n = size(words);
     32         for (int i = 0; i < n; i++) {
     33             for (const char c : words[i]) {
     34                 const int idx = c - 'a';
     35                 count[i][26] += score[idx];
     36                 count[i][idx]++;
     37             }
     38         }
     39 
     40         for (const char c : letters) {
     41             const int idx = c - 'a';
     42             count[n][26] += score[idx];
     43             count[n][idx]++;
     44         }
     45 
     46         return rec(n);
     47     }
     48 };
     49 
     50 int Solution::count[16][27];