Counting Words With a Given Prefix - Leetcode 2185 - Python

0:00 - Read the problem
0:30 - Brute Force
5:05 - Trie Explanation
9:33 - Trie coding

leetcode 2185

#neetcode #leetcode #python

[Everafterbreak_]

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

[johanavril]

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.

[chaitanyayeole]

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

[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.

[KarthiKarthi-dfmp]

Waiting for today's Problem's solution explanation

[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 So I think we have to store like pair (we have only one option) in each node of trie. Any body tried that

[Сергей-еэн]

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

[ibrahimnaser]

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

[ngneerin]

The prefix tree solution is terrible option for this problem

[pastori]

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

[freecourseplatformenglish]

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

[EranM]

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