Counting Words With a Given Prefix - Leetcode 2185 - Python

[@staywithmeforever]

January month ❌ Prefix month ✅

[@Everafterbreak_]

yes guys we know Trie is not the best option but we can use an easy question to practice it.

[@johanavril1691]

the prefix tree implementation will always be slower than the naive one for this task. It could only be faster if you are counting occurences for many different prefixes on a set of words and not recreating the prefix tree for every different prefix.

[@dj_jiffy_pop]

Data point on naive approach... ran the following brute force loop-n-regex across /usr/share/dict/words, which is a list of 235,976 words: #!/usr/bin/perl use Time::HiRes qw(gettimeofday tv_interval); $"=" "; my @prefix=@ARGV; my $words=[]; my $matches={}; while(defined($_ = )) { chomp; push @$words,$_; } my $t0=[gettimeofday]; map { my $p=$_; my @m=grep { /^${p}/ } @$words; $matches->{$p}=\@m; } @prefix; my $ms = (tv_interval $t0,[gettimeofday])*1000.0; foreach (keys %$matches) { print "Prefix: $_ "; my @m=@{$matches->{$_}}; print "Num matches: ".scalar(@m)." "; print "Matches: @m "; } print "Total match time: ${ms}ms "; Just timing the match portion across all prefixes... "cat /usr/share/dict/words | ./bs.pl foo" finds 116 matches in 45ms... for "foo bar" finds 116 and 389 matches in 90ms... for "foo bar baz" finds 116, 389, and 5 matches in 134ms... pre-shuffling the list doesn't change the result, of course... this is on 2021 13" basic M1 Pro, so not exactly beefy...

[@UppityAfrican-n2t]

I care for the minor details and find them fascinating. Sets your channel and content apart.

[@Hoppitot]

yea I wanted to do some SQL leetcodes and having some random dude that didnt have a clue about teaching trying to make a tutorial made me appreachiate neetcode more

[@UppityAfrican-n2t]

@@Hoppitot I appreciate the options the brute force for novices and also skills a seasoned engineer uses to approach the questions. He's very good at typing it back to specific concepts and this is a one stop shop he has videos to further delve into concept. The gold is the things he thinks are boring or nerdy. Sure it's complex at this stage but, I have it in memory and can revisit it. Basically I wanted to drive the point home the "sauce is saucing", please don't fix what's not broke. If some complained maybe do the additional information as bonus material every other video.

[@chaitanyayeole4111]

@NeetCodeIO I find these smaller details fascinating. It forces you to thing of optimization in every scenario.

[@rode_atharva]

Thank you❤❤❤

[@Сергей-е5э3н]

Hello, can you please make a video on the problem 3409 "Longest Subsequence With Decreasing Adjacent Difference"?

[@ngneerin]

The prefix tree solution is terrible option for this problem

[@CashmereLifestyle]

Why bother adding words to the trie if we only really care about the prefix word? In my trie solution I only added the prefix word, and went through each word in the list and went character by character, checking if it was in the trie. If the character was not in the trie, that means it's not a prefix. If we come across the end of the prefix word, then we can add 1 to our result. That way, we skip words immediately once we know they're not prefixes and only increment the result once we loop through the prefix of the word.

[@5p7Ro0t]

Ah! Its a great approach. I tried it and reduced the runtime from 55ms to 3ms. Thanks Bro.

[@FraxeFelipe]

This way you end up with the brute force approach

[@orepajic2625]

the trie solution is actually less efficient than brute force, so your optimization brings it down to brute force, kinda doesnt make sense to do prefix tree for this problem

[@prajapati-suraj]

in yesterday's problem i tried to create two separate tries prefix_trie and suffix_trie and tried to insert the each word in prefix_trie and reverse of the word in suffix_trie and tried to count how many of these words start and end with pref given in the problem statement. But, it didn't work that you said would work in the last video....... So I think we have to store like pair (we have only one option) in each node of trie. Any body tried that ...................

[@ibrahimnaser5233]

does anyone know how his editor on leetcode is in dark mode?

[@salarystealer]

nice

[@harmsingh6383]

1st 😊

[@pastori2672]

tries don't make sense here it's not even overkill it's just unnecessary, we go from n * m time to n * l + m time which is probably pretty much the same for most test cases + we go from constant space to n * l + the overhead it's just doesn't make sense

[@orepajic2625]

if i understood his optimization correctly, the trie solution is slower than brute force, because even with the optimization it comes to m*n +n while brute is just m*n

[@freecourseplatformenglish2829]

This solution Beats - 100% class Solution: def prefixCount(self, words: List[str], pref: str) -> int: res = 0 N = len(pref) for word in words: if len(word) < N: continue if word[0:N] == pref: res += 1 return res

[@MarkTheSWE]

When will you do a new language

[@EranM]

bruh.. just sum(1 if word.startswith(pref) else 0 for word in words)