We use cookies to ensure you have the best browsing experience on our website. Please read our cookie policy for more information about how we use cookies.
- Hash Tables: Ransom Note
- Discussions
Hash Tables: Ransom Note
Hash Tables: Ransom Note
Sort by
recency
|
1917 Discussions
|
Please Login in order to post a comment
I haven't seen any Python Solutions that are O(m) + O(n) in time yet that do not simply use an external library to solve the problem. I've included my solution below. First, in O(m), we go through the magazine word by word and check if it is in the dictionary. If it already is, we increment the value stored under this key word by one. If not, we add it to the dictionary. Second, in O(n) time, we work down the note word by word, decrementing the values in the dictionary. If we get a negative value (more instances of that word in the note than the magazine), we set a flag to zero. If any word is not in the dictionary (a word in the note not in the magazine), we also set the flag to zero. Finally, we return the answer yes based if the flag was untouched, and no in the cases above. This solution takes O(m) space.
def checkMagazine(magazine, note): f = 1 dic = {} for i, v in enumerate(magazine): try: dic[v] += 1 except KeyError: dic[v] = 1
one of the easyeast solution is
for(String s:note){ if(!magazine.remove(s)){ System.out.println("No"); break; }else if(s==note.get(note.size()-1)){ System.out.println("Yes"); } }
Java
Initially I went for the following naive implementation but I noticed it's slow:
but then I used maps:
Python