Can Anybody give me the sample code of implementation of basic trie using multidimensional arrays. I saw various programmers using this. And i personally feel i will be a lot more comfortable in handling arrays than using node pointers in tries.
# | User | Rating |
---|---|---|
1 | tourist | 3757 |
2 | jiangly | 3647 |
3 | Benq | 3581 |
4 | orzdevinwang | 3570 |
5 | Geothermal | 3569 |
5 | cnnfls_csy | 3569 |
7 | Radewoosh | 3509 |
8 | ecnerwala | 3486 |
9 | jqdai0815 | 3474 |
10 | gyh20 | 3447 |
# | User | Contrib. |
---|---|---|
1 | maomao90 | 171 |
2 | awoo | 165 |
3 | adamant | 163 |
4 | TheScrasse | 159 |
5 | maroonrk | 155 |
6 | nor | 154 |
7 | -is-this-fft- | 152 |
8 | Petr | 147 |
9 | orz | 146 |
10 | pajenegod | 145 |
Can Anybody give me the sample code of implementation of basic trie using multidimensional arrays. I saw various programmers using this. And i personally feel i will be a lot more comfortable in handling arrays than using node pointers in tries.
Name |
---|
Auto comment: topic has been updated by Terror_404 (previous revision, new revision, compare).
Auto comment: topic has been updated by Terror_404 (previous revision, new revision, compare).
can't it be implemented using an adjacency list? I don't remember exactly as I learnt it a long time ago but any information will be appreciated.
Here is a simple implementation problem and a solution with an array-based trie to this problem. The code should hopefully be clear enough for you to figure out what's happening.
You are given $$$n$$$ strings $$$s_1, s_2,\dots, s_n$$$. Let $$$S = {s_1, s_2,\dots, s_n}$$$.
You are also given $$$q$$$ strings $$$t_1, t_2,\dots, t_q$$$. For each $$$i = 1, 2,\dots, q$$$, find the longest common prefix of $$$t_i$$$ and any string in $$$S$$$.
Input: First line: number of test cases ($$$\le 10^4$$$)
Sum of string lengths is $$$\le 10^6$$$
Output: For each test case, $$$q$$$ integers: the lengths of the longest common prefixes.
great implementation
Nice implementation
Since all 26 'branches' are hardly used, it may be worth considering using a dynamically allocated array or set for the second dimension that holds the paths within the trie to save memory. $$$log\ 26$$$ or $$$log\ |branches|$$$ is constant, so this optimization will have no asymptotical difference.