data structures - C++ Boggle Solver: Finding Prefixes in a Set -

data structures - C++ Boggle Solver: Finding Prefixes in a Set -

this homework assignment, don't want exact code, appreciate ideas can help point me in right direction.

the assignment write boggle solving program. i've got recursive part downwards feel, need insight on how compare current sequence of characters dictionary.

i'm required store dictionary in either set or sorted list. i've been trying way implement using set. in order create programme run faster , not follow dead end paths, need check , see if current sequence of characters exists prefix in set (dictionary).

i've found set.find() operation returns true if string exact match. in lab requirements, professor mentioned that:

"if dictionary stored in set, many info construction libraries provide way find string in set closest 1 searching for. such operation used find word given prefix."

i've been searching today professor describing. i've found lot of info on tries, since i'm required utilize list or set, don't think work.

i've tried looking algorithms autocomplete functions, ones i've found seem extremely complicated i'm trying accomplish here.

i thinking of using strncmp() compare current sequence word dictionary set, again, don't know how function in situation, if @ all.

is worth go on investigating how work in set or should seek using sorted list store dictionary?

thanks

as @raymond hettinger mentions in answer, trie extremely useful here. however, if either uncomfortable writing trie or prefer utilize off-the-shelf components, can utilize cute property of how words ordered alphabetically check in o(log n) time whether given prefix exists. thought follows - suppose illustration checking prefix "thr." if you'll note, every word begins prefix "thr" must sandwiched between strings "thr" , "ths." example, thr ≤ through < ths, , thr ≤ throat < ths. if storing words in giant sorted array, can utilize modified version of binary search find first word alphabetically @ to the lowest degree prefix of selection , first word alphabetically @ to the lowest degree next prefix (formed taking lastly letter of prefix , incrementing it). if these same word, nil between them , prefix doesn't exist. if they're not, between them , prefix it.

since you're using c++, can potentially std::vector , std::lower_bound algorithm. throw words std::set , utilize set's version of lower_bound. example:

std::set<std::string> dictionary; std::string prefix = /* ... */ /* next prefix. */ std::string nextprefix = prefix; nextprefix[nextprefix.length() - 1]++; /* check whether there prefix. */ if (dictionary.lower_bound(prefix) != dictionary.lower_bound(nextprefix)) { /* ... has prefix ... */ } else { /* ... no word has prefix ... */ }

that said, trie improve construction here. if you're interested, there info construction called dawg (directed acyclic word graph) similar trie uses substantially less memory; in stanford introductory cs courses (where boggle assignment), students provided dawg containing words in language. there info construction called ternary search tree somewhere in-between binary search tree , trie may useful here, if you'd it.

hope helps!

c++ data-structures set prefix