How do I search a list of words? Kinda like a dictionary

Question

Im trying to search a text file that contains a list of words, the user will input the first couple characters, "ab", and should print a ll possible words like abnormal, absent, etc..

Any ideas of how I should start this in c++ are much appreciated, thanks!!!

Answer 1

This is an interesting question because you can do two things:

1) You can do a sequential search using a while loop:
- If string[0]+string[1] == 'ab' (for example), return word.
- Iterate through the entire text file using this function and it'll return all of the words with that prefix.
- This can take a pretty long time. if you're looking for a word that begins with the letters 'zz', it'll have to look at every word in the dictionary until it reaches 'z' and then every word that begins with 'z' to find one that begins with 'zz'. Not optimal.

2) You can load the text file into a Trie (aka prefix tree)!
- This is a moderately advanced data structure, but it's easy enough to learn 😉
- Essentially you load the words onto a tree where each node is a portion of a word. For example, 'app', 'apple', and 'application' all begin with the same letters, so they follow the same branch of the tree.
- What's really wild about this is that, once you load the dictionary file into this data structure, it only takes N steps to find a word, where N is the length of the word. Looking for the word 'zz', for example, would mean you just have to go to the 'z' node, then branch down to the next 'z'. Two steps!
- https://en.m.wikipedia.org/wiki/Trie should help more than I can in this matter.

Best of luck!

Answer 2

Read single words and check if they have the character sequence in them.

Here is a way how to read words out of a file:
https://stackoverflow.com/questions/44750829/c-read-file-word-by-word-without-any-symbol