0

If I were to implement a word processor's spelling checker, which would be more efficient implementation? The dictionary needs frequent retrievals and occasional insertions. Since there is no maximum number of dictionary items, BST would be a better choice. But it also needs frequent retrievals and a hash table has faster search operation time. What would be the better answer in this case?

JJTO
  • 847
  • 2
  • 8
  • 13
  • Are you intending to have this spell checker actually offer corrections, or just return a known-word/unknown-word flag for each word? – Blorgbeard Dec 15 '16 at 00:35
  • That wasn't specified in the question... I guess if you needed to offer corrections, you would neeed to support a fast ordered traversal operations, so a BST would be the best choice. – JJTO Dec 15 '16 at 00:40
  • 1
    I know it wasn't, that's why I asked. It seems like a pretty useless spell checker without corrections. Are you actually making a spell-checker, or is this question just academic? Also, have you read this: http://norvig.com/spell-correct.html – Blorgbeard Dec 15 '16 at 00:43

1 Answers1

1

Since there is no maximum number of dictionary items, BST would be a better choice.

IMO, implementing a dictionary using BST would be a bad idea. Trie is the right option for you.

You can find the comparision between hashtable and trie here : How Do I Choose Between a Hash Table and a Trie (Prefix Tree)?

Community
  • 1
  • 1
Saurav Sahu
  • 13,038
  • 6
  • 64
  • 79