[google面试题]write a function that will return true if the ransom note can be made from the magazines; otherwise, it will return false
Pretty‐good answer:Make a data structure to store acount of each letter in themagazine string.If you're programming in C,you can make an array of length 256and simply use the ASCII value for each character as its spot in the array,sincecharacters are 1 byte.If you're programming in Java,you can just use a hashtableinstead(since characters are 2 bytes in Java).Then go through the magazine stringand for each character,increment the value for that letter in your data structure.After you go though the whole magazines tring,you should have an exact count ofhow many times each character appears in the magazine string.Then go througheach character in the ransom note string and for every character you encounter, decrement the value for that letter in your data structure.If you ever find that after you decrement acount to something less than 0,you know you can't make theransom note,so you immediately return false.If however you get though the entireransom note without running out of available letters,you return true.Even better answer:Because the magazine string may be very large,we want toreduce the time we spend going through the magazine string.We use the same ideaas above,except we go through the ransom note and the magazine string at thesame time.Keep one pointer for our current character in the ransom note andanother pointer for our current character in our magazine string.First,check to see if the count in our data structure for our current ransom note character is greater than 0.If it is,decrement it and advance the pointer in our ransom note.If it isn't,start going through the characters in the magazinestring,updating t he counts in the data structure for each characterencountered,until we reach the character we need for our ransom note.Then stop advancing the magazine string pointer and start advancing the ransom note pointeragain.If we get to the end of the ransom note,were turn true.If we get to the end of the magazine string(meaning we didn't findenough letters for our ransom note),we return false.
页:
[1]