leetcode

0 class Solution {

1 class Trie {

2 struct Node {

3 Node *children[26] = {nullptr};

4 int count = 0;

5 } node;

6

7 public:

8 void insert(const string &word) {

9 Node *crnt = &node;

10

11 for (const char c : word) {

12 const auto idx = c - 'a';

13 if (!crnt->children[idx]) crnt->children[idx] = new Node();

14 crnt = crnt->children[idx];

15 crnt->count++;

16 }

17 }

18

19 int count(const string &word) const {

20 const Node *crnt = &node;

21 int res = 0;

22

23 for (const char c : word) {

24 const auto idx = c - 'a';

25 crnt = crnt->children[idx];

26 res += crnt->count;

27 }

28

29 return res;

30 }

31 };

32

33 public:

34 vector<int> sumPrefixScores(const vector<string> &words) const {

35 vector<int> res;

36 Trie trie;

37

38 for (const auto &word : words)

39 trie.insert(word);

40 for (const auto &word : words)

41 res.push_back(trie.count(word));

42

43 return res;

44 }

45 };