Find Common Characters - Leetcode 1002 - Python

0:00 - Read the problem
0:30 - Drawing Explanation
7:20 - Coding Explanation

leetcode 1002

#neetcode #leetcode #python

[Juicysalad]

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

[adityamwagh]

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!

[twlight]

Just started to look at this problem and you just posted the video <3 fate

[chiragjoshi]

weird question. easier to solve, harder to code imo .

[BillyL]

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.

[vijethkashyap]

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!

[freecourseplatformenglish]

I solved it using 2 dict instead of Counter. I prefer close to native rather than using fancy Counter.

[sagar]

How can this be an 'easy' problem, is it just hard for me or what?

[tunno]

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

[kahafb]

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()

[benedictaamoah]

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

[bradleyhanson]

Not recommended, but lol python:

class Solution:
def commonChars(self, words: List[str]) -> List[str]:
return reduce(and_, map(Counter, words)).elements()

[AnordinaryMan]

I thought the same but coding this was kinda hard in cpp considering this is just an easy question

[athiyamanonep]

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 .

[Munchen]

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()

[RubyVA-gxcd]

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

[lakshyadhawan]

it would be great, if you would post the solution in other languages too, in the description maybe, your explainations are great

[DeathSugar]

worst thing that it returns array of strings instead of array of characters. the biggest performance eater out there

[Zmey]

My time is 7 ms and I beat 39.77% of users with Go.

[aemswe]

I do not fully understand why the space complexty is 1, can anyone clarify?