Given an unordered list of words, what's quickest way to test whether a certain word is in that list?
I can't think of another way to do this other than just going through each element in the list and checking whether it's the word I want.
$\begingroup$
$\endgroup$
3
-
2$\begingroup$ You can't do that faster. There is no way you can conclude that a word is not in the list without looking at all the input. A running time of $n$ for input size $n$ is optimal. $\endgroup$– AstridNeuCommented Sep 18, 2019 at 21:17
-
1$\begingroup$ If you need to solve the problem multiple times with the same dictionary but different words you can use a Trie to solve the problem in linear time in terms of the input. $\endgroup$– Marcelo FornetCommented Oct 18, 2019 at 5:33
-
$\begingroup$ What is the exact definition of your problem? Is the list, the word, or both part of your input? Do you need to solve the problem only once or for multiple lists (same word) / words (same list)? $\endgroup$– StevenCommented Oct 18, 2019 at 17:37
Add a comment
|
2 Answers
$\begingroup$
$\endgroup$
If you are given an unordered list and asked to test whether just one item is in the list then a sequential check of each item in the list is the best you can do.
If you want to carry out multiple tests (but you do not know all the test items in advance) then it is worth the initial overhead of sorting the list, creating a hash table, or creating a search tree.
$\begingroup$
$\endgroup$
2
It really depends on what data structure you want to use. If you are using an array, one way is to sort it in $O(n\log(n))$ and then you can check whether an item exists using binary search in $O(\log(n))$. One other way is to use hash tables data structures like dictionaries in Python where you can answer such question in $O(1)$. Check Python Dictionaries or C++ Maps.
-
$\begingroup$ No. $O(n\log n)$ is slower that what OP suggests. And a hash table still requires you to process all the input. $\endgroup$ Commented Sep 18, 2019 at 21:20
-
$\begingroup$ Hash tables will not guarantee O(1) worst case lookup time without special care. $\endgroup$– JuhoCommented Oct 18, 2019 at 15:31