In a technical interview i was asked to implement the t9 dictionary. I knew it can be done using tries, but didn't know how to go about it. Could anyone please explain it ?
Note: Don't mark it as duplicate due to this, as it doesn't contain any explanation.
Implementation of a t9 dictionary using trie
1.8k Views Asked by Prakhar Agarwal At
1
There are 1 best solutions below
Related Questions in DATA-STRUCTURES
- OpenLayer 3: Map pointer up event can not be triggered when the map created on overlay
- Angular scroll directive
- Setting multiple events in one ext.net button
- Detect if Application was suspended in OnNavigatedFrom for Windows Phone 8
- When in click a radio button, it scroll to the top. How to prenvent that?
- Event subscribed but null in child class (after threads initialize)
- How to get results each sec from "perf stat -d sleep 1000"
- How to register event for TextBox end editing
- Stop the installshield installation if a file is not found in vb.net
- How to capture the next event based on a condition
Related Questions in TRIE
- OpenLayer 3: Map pointer up event can not be triggered when the map created on overlay
- Angular scroll directive
- Setting multiple events in one ext.net button
- Detect if Application was suspended in OnNavigatedFrom for Windows Phone 8
- When in click a radio button, it scroll to the top. How to prenvent that?
- Event subscribed but null in child class (after threads initialize)
- How to get results each sec from "perf stat -d sleep 1000"
- How to register event for TextBox end editing
- Stop the installshield installation if a file is not found in vb.net
- How to capture the next event based on a condition
Related Questions in T9
- OpenLayer 3: Map pointer up event can not be triggered when the map created on overlay
- Angular scroll directive
- Setting multiple events in one ext.net button
- Detect if Application was suspended in OnNavigatedFrom for Windows Phone 8
- When in click a radio button, it scroll to the top. How to prenvent that?
- Event subscribed but null in child class (after threads initialize)
- How to get results each sec from "perf stat -d sleep 1000"
- How to register event for TextBox end editing
- Stop the installshield installation if a file is not found in vb.net
- How to capture the next event based on a condition
Trending Questions
- UIImageView Frame Doesn't Reflect Constraints
- Is it possible to use adb commands to click on a view by finding its ID?
- How to create a new web character symbol recognizable by html/javascript?
- Why isn't my CSS3 animation smooth in Google Chrome (but very smooth on other browsers)?
- Heap Gives Page Fault
- Connect ffmpeg to Visual Studio 2008
- Both Object- and ValueAnimator jumps when Duration is set above API LvL 24
- How to avoid default initialization of objects in std::vector?
- second argument of the command line arguments in a format other than char** argv or char* argv[]
- How to improve efficiency of algorithm which generates next lexicographic permutation?
- Navigating to the another actvity app getting crash in android
- How to read the particular message format in android and store in sqlite database?
- Resetting inventory status after order is cancelled
- Efficiently compute powers of X in SSE/AVX
- Insert into an external database using ajax and php : POST 500 (Internal Server Error)
Popular # Hahtags
Popular Questions
- How do I undo the most recent local commits in Git?
- How can I remove a specific item from an array in JavaScript?
- How do I delete a Git branch locally and remotely?
- Find all files containing a specific text (string) on Linux?
- How do I revert a Git repository to a previous commit?
- How do I create an HTML button that acts like a link?
- How do I check out a remote Git branch?
- How do I force "git pull" to overwrite local files?
- How do I list all files of a directory?
- How to check whether a string contains a substring in JavaScript?
- How do I redirect to another webpage?
- How can I iterate over rows in a Pandas DataFrame?
- How do I convert a String to an int in Java?
- Does Python have a string 'contains' substring method?
- How do I check if a string contains a specific word?
1)Build a trie(add all words from dictionary to it).
2)Initially a current node is a root of the trie.
3)When a new character is typed in, you can simply go to the next node from the current node by the edge that corresponds to this character(or report an error if there is nowhere to go).
4)To get all(or
k
first) possible words with a given prefix, you can just traverse the trie in depth first search order starting from the current node(if you need onlyk
first words, you may stop the search whenk
words are found).5)When the entire word is typed in and a new word is started, move to the root again and repeat the steps 3) - 5) for the next word.
P.S All nodes that correspond to a word(not a prefix of a word, but an entire word) can be marked when the trie is build so that it is easy to understand whether a new word is found or not when you traverse the trie during the step 4).