leetcode

0 class Trie {

1 struct Record {

2 bool end;

3 array<Record *, 26> records = {nullptr};

4

5 Record *insert(int x) {

6 if (records[x]) return records[x];

7 return records[x] = new Record();

8 }

9

10 Record *check(int x) { return records[x]; }

11 };

12

13 Record *record = new Record;

14 Record *last(string word) {

15 Record *crnt = record;

16 for (char c : word)

17 if (!crnt)

18 return nullptr;

19 else

20 crnt = crnt->check(c - 'a');

21 return crnt;

22 }

23

24 public:

25 void insert(string word) {

26 Record *crnt = record;

27 for (char c : word)

28 crnt = crnt->insert(c - 'a');

29 crnt->end = true;

30 }

31

32 bool search(string word) {

33 Record *crnt = last(word);

34 if (!crnt) return false;

35 return crnt->end;

36 }

37

38 bool startsWith(string prefix) { return last(prefix); }

39 };