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
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
|
// 1255. Maximum Score Words Formed by Letters
#include "leetcode.h"
/*
* given a list of 'words' list of single 'letters' (potentially repeating), and
* 'score' of every character. return the maximum score of any valid set of
* words formed by using the given letters ('words[i]' cannot be used two or
* more times). it is not necessary to use all characters in 'letters' and each
* letter can only be used once. score of letters a through z is given by
* 'score[i]' respectively.
*/
struct pair {
bool valid;
int len;
int score;
};
int process(char *str, int *hash, struct pair *p, int idx, bool *no_add) {
if (!(*no_add)) {
for (int i = 0; i < p[idx].len; i++)
hash[str[i] - 'a']++;
} else {
for (int i = 0; i < p[idx].len; i++) {
if (!hash[str[i] - 'a']) {
for (int j = 0; j < i; j++)
hash[str[j] - 'a']++;
return 0;
}
hash[str[i] - 'a']--;
}
*no_add = false;
}
return p[idx].score;
}
void dfs(char **words, int wordsSize, int *hash, struct pair *p, int *cnt,
int *res, int idx) {
if (idx == wordsSize) {
*res = fmax(*cnt, *res);
return;
}
for (int i = idx; i < wordsSize; i++) {
bool no_add = true;
if (p[i].valid)
*cnt += process(words[i], hash, p, i, &no_add);
dfs(words, wordsSize, hash, p, cnt, res, i + 1);
if (!no_add)
*cnt -= process(words[i], hash, p, i, &no_add);
}
}
int maxScoreWords(char **words, int wordsSize, char *letters, int lettersSize,
int *score, int scoreSize) {
int hash[26] = {0}, cnt = 0, ans = 0;
for (int i = 0; i < lettersSize; i++)
hash[letters[i] - 'a']++;
struct pair *p = (struct pair *)calloc(wordsSize, sizeof(struct pair));
for (int i = 0; i < wordsSize; i++) {
int n = strlen(words[i]), res = 1, tmp = 0;
p[i].len = n;
for (int j = 0; j < n; j++) {
tmp += score[words[i][j] - 'a'];
if (!hash[words[i][j] - 'a']) {
res = 0;
break;
}
}
p[i].valid = res;
p[i].score = !p[i].valid ? 0 : tmp;
}
dfs(words, wordsSize, hash, p, &cnt, &ans, 0);
free(p);
return ans;
}
int main() {
char *w1[] = {"dog", "cat", "dad", "good"},
*w2[] = {"xxxz", "ax", "bx", "cx"}, *w3[] = {"leetcode"},
*l1[] = {"a", "a", "c", "d", "d", "d", "g", "o", "o"},
*l2[] = {"z", "a", "b", "c", "x", "x", "x"},
*l3[] = {"l", "e", "t", "c", "o", "d"};
int s1[] = {1, 0, 9, 5, 0, 0, 3, 0, 0, 0, 0, 0, 0,
0, 2, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0},
s2[] = {4, 4, 4, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0,
0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 5, 0, 10},
s3[] = {0, 0, 1, 1, 1, 0, 0, 0, 0, 0, 0, 1, 0,
0, 1, 0, 0, 0, 0, 1, 0, 0, 0, 0, 0, 0};
printf("%d\n",
maxScoreWords((char **)w1, ARRAY_SIZE(w1), (char *)l1, ARRAY_SIZE(l1),
s1, ARRAY_SIZE(s1))); // expect: 23
printf("%d\n",
maxScoreWords((char **)w2, ARRAY_SIZE(w2), (char *)l2, ARRAY_SIZE(l2),
s2, ARRAY_SIZE(s2))); // expect: 27
printf("%d\n",
maxScoreWords((char **)w3, ARRAY_SIZE(w3), (char *)l3, ARRAY_SIZE(l3),
s3, ARRAY_SIZE(s3))); // expect: 0
}
|