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

Question

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.

You can loop through your array, and for each item, use indexOf() or equivalent method to find out did the letter contain on that string — Doan Cuong
– Doan Cuong, Commented Apr 3, 2013 at 1:50
Is there a clever way Would you prefer answers from .net ? — Rajaprabhu Aravindasamy
– Rajaprabhu Aravindasamy, Commented Apr 3, 2013 at 9:26

Pyrce · Accepted Answer · 2013-04-03 01:53:26Z

3

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.

answered Apr 3, 2013 at 1:53

Pyrce

8,5713 gold badges33 silver badges47 bronze badges

Sign up to request clarification or add additional context in comments.

Collectives™ on Stack Overflow

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

1 Answer 1

Comments

Your Answer

Hot Network Questions

Collectives™ on Stack Overflow

1 Answer 1

Comments

Your Answer

Sign up or log in

Post as a guest

Related