CODEWITHSUNDEEP
arraysperformancealgorithmsearch
J L
J L

Reputation: 2297

Algorithm to find specific char/letter in array of strings?

So I'm trying to come up with a algorithm to find words with a specific char/letter in an array of strings.

If I want words with vowel e, I would get word apple and hello from below set.

{apple, bird, hello}

To find words with specific character, will I need to look through all of the letters in the array and look through every character of each word?

Is there a clever way maybe by sorting the list and then searching somehow?

Also, what would be the running time of this algorithm? Will it be considered as O(n) or O(n*m)? Where n is the number of words in the dictionary and m is the length of each word in the array.

Upvotes: 1

Views: 1299

Answers (1)

Pyrce
Pyrce

Reputation: 8571

In order to find words with a specific character you need to read that character at least once. Thus you must reach each character from each word once, giving a runtime of O(n*m), where n is the number of words and m is the average word length. So yes, you need to lookup each character from each word.

Now if you're going to be doing lots of queries for different letters you can do a single pass over all words and map those words to the characters they are apart of. i.e. apple => a, p, l, e sets. Then you would have 26 sets which hold all words with that character ('a' : [apple], 'b' : [bird], 'c' : [], ... 'l' : [apple, hello], ...). As the number of queries increases relative to the size of your word set you would end up with an amortized lookup time of O(1) -- though you still have a O(n*m) initialization complexity.

Upvotes: 3

Related Questions