leetcode

0 // Only Trie

1 class MapSum {

2 struct Node {

3 Node(){};

4 Node *children[27] = {nullptr};

5 int &value = reinterpret_cast<int &>(children[0]);

6 int trail = 0;

7 };

8

9 Node *trie = new Node();

10

11 public:

12 void insert(const string &key, int val) {

13 Node *prev = trie;

14 for (const char c : key) {

15 const int idx = c & 0x1F;

16 if (!prev->children[idx]) {

17 prev = nullptr;

18 break;

19 };

20 prev = prev->children[idx];

21 }

22

23 const int diff = prev ? val - prev->value : val;

24

25 Node *crnt = trie;

26 for (const char c : key) {

27 const int idx = c & 0x1F;

28 crnt->trail += diff;

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

30 crnt = crnt->children[idx];

31 }

32 crnt->value = val;

33 }

34

35 int sum(const string &prefix) const {

36 const Node *crnt = trie;

37 for (const char c : prefix) {

38 const int idx = c & 0x1F;

39 if (!crnt->children[idx]) return 0;

40 crnt = crnt->children[idx];

41 }

42 return crnt->value + crnt->trail;

43 }

44 };

45

46 // Trie + hash map

47 class MapSum {

48 struct Node {

49 Node(){};

50 Node *children[27] = {nullptr};

51 int &value = reinterpret_cast<int &>(children[0]);

52 };

53

54 Node *trie = new Node();

55 unordered_map<string, int> um;

56

57 public:

58 void insert(const string &key, int val) {

59 const int diff = val - um[key];

60

61 Node *crnt = trie;

62 for (const char c : key) {

63 const int idx = c & 0x1F;

64 crnt->value += diff;

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

66 crnt = crnt->children[idx];

67 }

68 crnt->value += diff;

69 um[key] = val;

70 }

71

72 int sum(const string &prefix) const {

73 const Node *crnt = trie;

74 for (const char c : prefix) {

75 const int idx = c & 0x1F;

76 if (!crnt->children[idx]) return 0;

77 crnt = crnt->children[idx];

78 }

79 return crnt->value;

80 }

81 };