leetcode

0 class Solution {

1 static int count[16][27];

2 mutable array<int, 26> crnt{0};

3

4 int rec(const int n, const int idx = 0, const int score = 0) const {

5 if (idx == n) return score;

6

7 int res = rec(n, idx + 1, score);

8 auto back = crnt;

9 for (int i = idx; i < n; i++) {

10 bool valid = true;

11 for (int j = 0; j < 26; j++) {

12 crnt[j] += count[i][j];

13 if (crnt[j] > count[n][j]) {

14 valid = false;

15 break;

16 }

17 }

18 if (valid) res = max(res, rec(n, i + 1, score + count[i][26]));

19 crnt = back;

20 }

21

22 return res;

23 }

24

25 public:

26 int maxScoreWords(const vector<string> &words, const vector<char> &letters,

27 const vector<int> &score) const {

28 memset(count, 0x00, sizeof(count));

29

30 const int n = size(words);

31 for (int i = 0; i < n; i++) {

32 for (const char c : words[i]) {

33 const int idx = c - 'a';

34 count[i][26] += score[idx];

35 count[i][idx]++;

36 }

37 }

38

39 for (const char c : letters) {

40 const int idx = c - 'a';

41 count[n][26] += score[idx];

42 count[n][idx]++;

43 }

44

45 return rec(n);

46 }

47 };

48

49 int Solution::count[16][27];