World's most popular travel blog for travel bloggers.

Algorithm to efficiently determine whether a magazine contains all the letters in a search string

, , No Comments
Problem Detail: 

Title pretty much states the question, I was looking for some assistance with the following:

You are given a search string and a magazine. You seek to generate all the characters in a search string by cutting them out form the magazine. Give an algorithm to efficiently determine whether a magazine contains all the letters in a search string.

I wrote: "Create a count sort which just buckets every occurrence of each specific letter in the magazine down the line. Then use that to compare vs. the search string. If the magazine contains all the letters in the search string, then great you're done; otherwise you need a new magazine."

I feel like that's not enough of an answer for this problem, can someone help? Thanks!

Asked By : Speakmore

Answered By : gnasher729

If this was a real life problem, and the search string contained n letters, while the magazine contained m letters, then this would take O (n + m) in time. Typically you would assume that n is very small compared to m, so this solution would take a lot more time than needed.

I'd create a counted set of the letter in the search string. If that counted set is empty (because the search string was empty) I'm done. Then iterate through the letters in the magazine; if a letter is in the counted set then remove it and I'm done if the set became empty. Otherwise, if the iteration finishes then I have a counted set of all letters that cannot be provided by the search string.

This will usually end quite quickly, long before all the letters in the magazine are examined.

Best Answer from StackOverflow

Question Source :

3200 people like this

 Download Related Notes/Documents


Post a Comment

Let us know your responses and feedback