Ransom Note - Leetcode 383 - Hashmaps & Sets (Python)

[@GregHogg]

Master Data Structures & Algorithms For FREE at AlgoMap.io!

[@anshpradhan1954]

in my opinion, your roadmap website and the videos you put out are so under rated, your content is A level, and so far the best tutor of DSA in python in the entire community i have encountered, you are doing great work Greg 👍👍👍

[@RojinSharma-c8l]

Great explanation! Very well explained. Loved how you explained even the different approach, and sticked with the one that's best for the interviews. Thank you

[@boringhuman9427]

dict.get(value,defalult value) - It can eliminate the requirement of defaultdict

[@spider-capgaming1487]

Is it better to have a dictionary of the characters in magazine and loop over ransomNote or vice versa or is it basically the same?

[@venzdrop]

There is no exactly one solution to a problem. There are multiple solutions to solve one problem(I'm not saying every single problem because some problems require only one solution, and some require a lot of solutions). Rule number -> "if the code works, don't touch it." Yes, you can. Have a good day.

[@gaganlonde7190]

why can you store the chars of magazine in a list and loop over the chars of RansomNote and check if they in list if yes remove it from the list and if not return false as the ransomNote cant be made?

[@venzdrop]

yes, you can. i tried your question and coded it and it worked for the first three examples of leetcode I tried on vscode, but I didn't submit on leetcode yet. imma do it later. did it work for you?. There is no exactly one solution to a problem. There are multiple solutions to solve one problem(I'm not saying every single problem because some problems require only one solution, and some require a lot of solutions). Rule number -> "if the code works, don't touch it." Yes, you can. Have a good day.

[@aki_blasco]

Wouldn't space complexity be O(m) as you said in the video? Because it would be the number of key-value pairs from the counter that can hold at most O(m) unique characters from the magazine. I do not get why it would be O(1) space complexity.

[@Harry-em7km]

It is O(26) at most if magazine has every letter in the alphabet, so we can just call it constant. Reason it's not O(m) is because even if magazine is a really long string (m >> 26), the counter will still only ever have 26 keys at most

[@user_sense]

where do you get these problems from?

[@GregHogg]

They're all from leetcode

[@hlubradio2318]

His brain? No. Leetcode

[@venzdrop]

@@hlubradio2318 lol

[@MrIrishBoss]

Keeping it simple, just want to make sure there are enough of each letter in the magazine. for i in set(ransomNote): if magazine.count(i) < ransomNote.count(i): return False return True

[@mo_1023]

While it's more elegant and concise, it's an inefficient solution that has a time complexity of O(n * m) .. because magazine.count(i) searches the entire string in O(n), and then for every letter in ransom_note, your doing that magazine.count(i) .. if the length of ransom_note is m, then we have O(n * m) .. for large text it will consume a lot of memory and run slow

[@mjanish9836]

Good Explanation !! ThankYou

[@GregHogg]

Glad to hear it! You're very welcome :)

[@Ivan-Shyriaiev]

Thanks 🫡

[@lakshyamathur8808]

Couldn't it be solved using substring method ??

[@GregHogg]

What's that?

[@lakshyamathur8808]

@@GregHogg isn't there a method to check if string A is substring of string B?

[@zfarahx]

@@lakshyamathur8808 what's the point of studying DS&A if you're just using helper methods? Also, you can just Google that question, it's the most basic question ever.

[@lakshyamathur8808]

@@zfarahx ok bro 🙏♥️♥️

[@mstinku9003]

class Solution: def canConstruct(self, r: str, m: str) -> bool: k=Counter(r) l=Counter(m) return k

[@mstinku9003]

U CAN LITERALLY COMPARE COUNTERS DIRECTLY from collections import Counter counter1 = Counter([1, 2, 3]) counter2 = Counter([1, 2, 2, 3, 3, 3]) print(counter1

[@hlubradio2318]

Very nice as always

[@GregHogg]

Glad to hear it!

[@qulinxao]

return not(Counter(ransomeNote)-Counter(magazin))

[@venzdrop]

1 liners fr lmao. yall crazy. it worked.

[@brianwkinyua]

wow! 👍

[@khalidhussien6764]

standard array is a little quicker since the input is lower case english letters. int arr[26]; int pos = 0; for(char letter : magazine) { pos = letter - 97; arr[pos]++; } for(char letter : ransomNote) { pos = letter - 97; if(arr[pos] != 0) arr[pos]--; else return false; } return true;