Trie longest prefix matching

Question

I didn't get the end of the word concept in trie. I think my understanding of trie itself is incomplete. Can someone please explain the following piece in the code HERE

// If this is end of a word, then update prevMatch
               if( crawl.isEnd() ) 
                    prevMatch = level + 1;

Answer 1

This occurs when the code is climbing the trie searching for the longest prefix for a gifen word.

Say you have a trie that already contains the words:

"of" "one" "once"

and you are trying to search for the longest prefix of "onerous", which you would expect to come out at 3 (i.e. "one" is the longest prefix already present.

The code being executed reads:

    // See if there is a Trie edge for the current character
    if (child.containsKey(ch)) {
        result += ch;          //Update result
        crawl = child.get(ch); //Update crawl to move down in Trie

        // If this is end of a word, then update prevMatch
        if (crawl.isEnd()) {
            prevMatch = level + 1;
        }
    } else {
        break;
    }

so imagine you are looking at the "n" of "onerous". You discover that "on" is in the trie as a fragment but is not an end (because you have not put the word "on" in the trie but the word "one" is in there). This code will continue climbing the tree with the next character "e" but will not change prevMatch. When it looks at the "e" however, there is a match in the tree and it is an end because the word "one" is in the tree so this code stores 3 in prevMatch.

Answer 2

The IsEnd killswitch is set when the word ends but it's not the end of the trie or the search. The words are stored lexicographical into a tree or hashmap. It can happen the search word is not the first or second killswitch.