0
$\begingroup$

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!

$\endgroup$
  • 1
    $\begingroup$ We discourage "please check whether my answer is correct" questions, as only "yes/no" answers are possible, which won't help you or future visitors. See here and here. Can you edit your post to ask about a specific conceptual issue you're uncertain about? As a rule of thumb, a good conceptual question should be useful even to someone who isn't looking at the problem you happen to be working on. If you just need someone to check your work, you might seek out a friend, classmate, or teacher. $\endgroup$ – David Richerby Nov 1 '16 at 8:46
  • $\begingroup$ @DavidRicherby Considering I just picked up a book at Barnes and Nobles and am reading it, followed by evaluating the end of chapter questions to test my knowledge/recollection of things, it'd be difficult to ask the author (my teacher?) for the assistance. Doesn't help me that he didn't put any of the answers in the back of the book. But I'll make sure to send him an email asking for a response to my question. $\endgroup$ – Speakmore Nov 1 '16 at 12:44
  • $\begingroup$ What David is suggesting is that, among other things, we don't have enough information to give a helpful answer to your question. Exactly why do you feel that your answer isn't sufficient? What seems to be the problem with your answer? Those are questions we can answer. $\endgroup$ – Rick Decker Nov 1 '16 at 23:39
  • $\begingroup$ Because typically the answer to an algorithm is a little more in-depth than "create a bucket, store letters, compare" @RickDecker $\endgroup$ – Speakmore Nov 1 '16 at 23:47
1
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ Thanks for your response, I see how my algorithm isn't O(n) and how yours is considering it just iterates down O(n) elements in the magazine and nothing more! $\endgroup$ – Speakmore Nov 1 '16 at 12:53

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.