Find Common Characters - Leetcode 1002 - Python
Vložit
- čas přidán 24. 07. 2024
- 🚀 neetcode.io/ - A better way to prepare for Coding Interviews
🧑💼 LinkedIn: / navdeep-singh-3aaa14161
🐦 Twitter: / neetcode1
⭐ BLIND-75 PLAYLIST: • Two Sum - Leetcode 1 -...
Problem Link: leetcode.com/problems/find-co...
0:00 - Read the problem
0:30 - Drawing Explanation
7:20 - Coding Explanation
leetcode 1002
#neetcode #leetcode #python - Věda a technologie
I had exactly this approach, took me some time to think of it though and I wasn't sure if it was optimal or not. I guess it was
weird question. easier to solve, harder to code imo .
if you know python its pretty easy.
@@chrischika7026python is the Very Easy path for most of these
I basically made a 26 x num_words array i.e. a row for each alphabet, and then for each row I calculated the minimum value in the row, and added min_value * char to the result array. So basically a O(26 * n) time and O(26 * n) space solution. I was worrying about the zero but turns out I didn't need that character if it's count is zero!
Same here!
The worst case runtime should be O(n * m) where n = num_words and m = avg. length of a word? If your filling those rows
Great explanation again. Thank you.
Just started to look at this problem and you just posted the video
I created a table for the first word with letters as the key and the values as the count. Then for each subsequent word, if the letter exists, I replaced the value in the first table with the minimum count of the new table and the first table. If the letter doesn't exist, I set the key's value to 0 in the first table, using it as a flag that it doesn't exist in all tables. Once you have the first table fully completed, there should be 0s which indicate that a letter doesn't exist in all the dictionaries. Then you iterate through the first table and anything that is a value > 0 means it exists in all tables, so you just for loop through it and generate the answer using the keys.
I thought the same but coding this was kinda hard in cpp considering this is just an easy question
Surprised that std doesn't have a find_nth function.
@@Dannnneh you have to implement these by yourself that's why I don't like cpp for DSA.
yeah . I think I should start learning python
Learnt we can iterate over Counters directly instead of doing dict.items(). Also that while iterating over counter, it doesn't give key errors and just assigns count to zero in case the key wasn't found! Pretty NEET I must say!
I did exactly the same way, except i used tmp hash map to get min count values from cnt and curcnt and put it back in cnt .lol i could have avoided it .
I solved it using 2 dict instead of Counter. I prefer close to native rather than using fancy Counter.
🥳🥳👋 Thanks for sharing!
Dude plz also do solution in C++..........
Perfect ❤
Hii thank you for the video today,your tutorials are super helpful and it's always nice watching you code out your solutions. I coded out a simpler solution that I wanted to share with you if you don't mind that I think is shorter and more efficient. I'm open to feedback as well
class Solution:
def commonChars(self, words: List[str]) -> List[str]:
results = []
for char in set(words[0]):
count = min(word.count(char) for word in words)
results += [char] * count
return results
is using a counter the same as using 2 hashmaps?
class Solution:
def commonChars(self, words: List[str]) -> List[str]:
n = len(words)
res = []
h1 = defaultdict(int)
for i in range(n):
h2 = h1
h1 = defaultdict(int)
for j in range(len(words[i])):
h1[words[i][j]] += 1
if i > 0:
for c in h1:
h1[c] = min(h1[c], h2[c])
for c in h1:
while h1[c] > 0:
res.append(c)
h1[c] -= 1
return res
How can this be an 'easy' problem, is it just hard for me or what?
Ok, I was able to do it in O(n square), and O(n) space, let's see how I should do it the right way
I made thus:
counter = Counter(words[0])
for i in range(1, len(words)):
counter_2 = Counter(words[i])
counter &= counter_2
return counter.elements()
I do not fully understand why the space complexty is 1, can anyone clarify?
same, thought cnt hashmap uses space
It's because the counter dictionary will at most have 26 keys (the number of letters in the alphabet), meaning its space complexity is O(26), which in other words is constant and therefore O(1) space
it would be great, if you would post the solution in other languages too , in the description maybe, your explainations are great
such a stupid comment
worst thing that it returns array of strings instead of array of characters. the biggest performance eater out there
class Solution:
def commonChars(self, words: List[str]) -> List[str]:
count = Counter(words[0])
for i in range(1, len(words)):
count &= Counter(words[i])
return count.elements()
My time is 7 ms and I beat 39.77% of users with Go.
Not recommended, but lol python:
class Solution:
def commonChars(self, words: List[str]) -> List[str]:
return reduce(and_, map(Counter, words)).elements()
can u mentor me
Why does neetcode always sound angry 😅
Rip coding this in js