0
$\begingroup$

I am trying to optimize a program, where I need to know whether a given set of keywords present in the set of words. I believe using the dictionary is the only way to optimize it. Any other technique so that I can get better time complexity? The below python script is my version of the code, this works for a small sentence with a time complexity O(len(keywords)) + O(frequency_table CONSTRUCTION TIME). Space complexity is not a problem, but time.

def cover_test(keys, sentence):
    frequency_table = collections.Counter(sentence)
    count = 0
    for key in keys:
        if key in frequency_table:
            count += 1
    return count == len(keys)

cover_test("word1 word4".split(), "word2 word1 word3 word4".split())
# output 
# True, because word1 and word4 is present in the sentense 

examples of input

Set of words

['apple', 'green', 'horse', 'ink', 'ball', 'cat', 'dog', 'elephant', 'fun']

Set of keywords

['fun, 'green']

Output for the above input is True

Update: More clarifications: The goal is to ensure that every word from the keys list is included in the sentence list, in linear or less time complexity.

$\endgroup$
  • $\begingroup$ What do you mean by cover of keywords in a sentence? $\endgroup$ – Pål GD Dec 27 '18 at 19:23
  • $\begingroup$ @PålGD if a set of words covers the sentence means, those words are present in the sentence at least once in any order. $\endgroup$ – ajayramesh Dec 27 '18 at 21:50
  • $\begingroup$ Then it sounds like the empty set covers every sentence since all words in the empty set "are present in the sentence at least once in any order." I'm guessing that's not a right interpretation. Please update your question with a formal definition of cover of keywords in the sentence. $\endgroup$ – Pål GD Dec 27 '18 at 21:59
  • $\begingroup$ I have updated the question and some example. Hope it gives more clarity. $\endgroup$ – ajayramesh Dec 28 '18 at 0:06
  • $\begingroup$ You still need to add a definition, it's still unclear to me. Do you want to say that you are given two lists of strings, "the words" and "the keywords", and the question is "Is every keyword a member of the words"? $\endgroup$ – Pål GD Dec 28 '18 at 0:16
1
$\begingroup$

I'm interpreting your question as wanting to quickly ensure that every word from the keys list is included in the sentence list.

Assuming you're using a sane version of python, the running time for the initial construction of the counter object is linear in the length of the sentence's description. At least as long as no word appears so many times that the integer stored in the counter exceeds INT_MAX.

So the overall running time, for sane inputs, is linear in the input, which is the best you can possibly expect (since Python has to read the entire input anyway, which takes linear time already).

That said, there's no compelling reason to use a counter here. You could just as easily have used a Set object and achieved the same running time without the assumption on word counts not exceeding a certain value. It might also be easier to read.

For example

def cover_test(keys, sentence):
    sentence_word_set = set(sentence)
    for key in keys:
        if key not in sentence_word_set:
            return False
    return True

or even

def cover_test(keys, sentence):
    sentence_word_set = set(sentence)
    return all(i in sentence_word_set for i in keys)

Set construction is promised to be expected linear-time in the size of sentence, with expected constant-time lookups. And the for loop goes through each key once (totalling to something linear in the size of keys) so the running time is expected linear in the whole input. Which again is the best you can do.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.