generated from threeal/project-starter
-
Notifications
You must be signed in to change notification settings - Fork 1
/
Copy pathsolution.c
53 lines (38 loc) · 1.54 KB
/
solution.c
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
#include <stdint.h>
#include <stdlib.h>
#include <string.h>
int dfs(int8_t** wordsCount, int wordsCountSize, int index, int8_t* lettersCount, const int* score);
int maxScoreWords(char** words, int wordsSize, char* letters, int lettersSize, int* score, int scoreSize) {
(void)scoreSize;
int8_t** wordsCount = malloc(wordsSize * sizeof(int8_t*));
for (int i = wordsSize - 1; i >= 0; --i) {
wordsCount[i] = malloc(26 * sizeof(int8_t));
memset(wordsCount[i], 0, 26 * sizeof(int8_t));
for (char* letter = words[i]; *letter != 0; ++letter) {
++wordsCount[i][*letter - 'a'];
}
}
int8_t lettersCount[26] = {0};
for (int i = lettersSize - 1; i >= 0; --i) {
++lettersCount[letters[i] - 'a'];
}
const int max = dfs(wordsCount, wordsSize, 0, lettersCount, score);
for (int i = wordsSize - 1; i >= 0; --i) free(wordsCount[i]);
free(wordsCount);
return max;
}
int dfs(int8_t** wordsCount, int wordsCountSize, int index, int8_t* lettersCount, const int* score) {
if (index >= wordsCountSize) return 0;
const int notPick = dfs(wordsCount, wordsCountSize, index + 1, lettersCount, score);
for (int i = 25; i >= 0; --i) {
if (wordsCount[index][i] > lettersCount[i]) return notPick;
}
int pick = 0;
for (int i = 25; i >= 0; --i) {
pick += score[i] * wordsCount[index][i];
lettersCount[i] -= wordsCount[index][i];
}
pick += dfs(wordsCount, wordsCountSize, index + 1, lettersCount, score);
for (int i = 25; i >= 0; --i) lettersCount[i] += wordsCount[index][i];
return notPick > pick ? notPick : pick;
}