Can anyone please explain how does trie work as 2d array and how it can be implemented that way. also explain how do we determine size of the array.
Trie as a 2d array works similar to a DFA (Finite automata). Just assume that you have a variable named counter that starts from 0 and it tracks the total memory locations that you have used till now. Then if your 2d trie is like trie[i][j] , it means that if you are at location numbered at i then if you are seeing the character j then what location number should I move to , the 2d trie stores this. So the total size is N * K where N is the sum of length of all the strings and K is the size of the character set. Initially the trie is set to -1 i.e. if trie[i][j] is -1 then it means you can’t perform any transition from state i if the next character is j. The variable counter is used to track how many locations you have used or simply it provides the index of the new node.
1 Like