Sum of Prefix Scores of Strings - Leetcode 2416 - Python

[@dhyeyparekh4994]

I loved the way you go from brute force to optimal thinking step by step. Great explanation

[@jamestwosheep]

I just wanted to express how grateful I am to your video explanations. I managed to go straight to that optimal solution with this one on my first attempt thanks in very large part to your previous explanations about prefix trees. I had relatively slow runtime too with my Javascript submission, but I suspect that may be because LeetCode might occasionally adds additional test cases over time to some of their problems.

[@adityamwagh]

I coded the optimal solution all by myself (without referring to the coding part of the video). Neet has designed his DSA course in in wonderful way. The video on PrefixTree definitely helped me!

[@AKProductionsTelugu]

Using a hashmap for the same trie approach seems to be working good with time complexity

[@_PranavDesai]

i suppose another optimisation would be to store the count of each prefix in a hashmap.

[@MP-ny3ep]

One of your best explanations. Thank you so much!

[@SergeyAngelov]

Sometimes I wonder what is the logic of problem classification. I would put it between easy and medium. There are a lot of medium problems that are way harder than this one. Literally took couple minutes to understand what is needed and couple minutes to code optimal solution using Trie.

[@sauravsingh4497]

I was using the older version of leetcode on phone so couldn't see the difficulty level of the problem I solved it on phone using trie
Didn't realise it was a hard problem.If I knew it was a hard problem I would have fumbled

[@ramennudeln247]

Those faster examples use a dict instead of a list in the TrieNode class which saves time and operations, it would seem.

[@vijethkashyap151]

BEAUTIFUL ! 💖

[@jitpatel7692]

Thank you,great explanation

[@karthi7102]

Thank you, explanaation was great.

[@ajitpalsingh606]

I did with hashmap 36/38 passed

[@TheLearningLab898]

same

[@vanshraj4724]

can someone tell why using vector gave mle but not ehen using array in cpp using Trie method

[@matheuscosta5330]

Nice!

[@SarweshParsewar]

Day 1 of asking to upsolve leetcode contest problems🤖

[@anandsrikumar007]

This is yesterday's problem only. Only small change is there.

[@GursimranMatharu]

why there are guitars in the thumbnail 😭

[@_lax.man_5473]

❤

[@steco5441]

Call variables pointers on purpose man please!!!!!! It could be a great inside joke

[@sanjeevmurmu6505]

i am trying to implement this solution in javascript but i am getting time limit exceeded on 37th testcase words=["bfiaaaaifb","aaaaooaaaa"] can anybody tell me how to optimize this further for javascript.

[@muditkalra7077]

yes i am also facing tle in js , i implement both approach (hashmap and trie) got tle on both solution!
Edit 1: I don't know why but i replace one for loop(getScore loop) with map and it somehow got accepted !

[@anshdholakia714]

I still dont get how the brute force solution is O(n^2.L^2)

[@professorpoke]

First tell me what is the complexity according to you. Then we can discuss further.

[@dekumidoriya-qi2is]

see it like this for comparison two loops -> O(n^2)
and for generating prefix -> O(L^2) beacause slicing is a O(n) operation
so TC -> O(n^2.L^2)

[@cineaddict1633]

@@dekumidoriya-qi2is in python slicing is o(1) operation

[@dekumidoriya-qi2is]

@@cineaddict1633 technically the complexity is not exactly O(1) it is O(k) where k is the size of slice
ref - wiki.python.org/moin/TimeComplexity

[@hasferrr]

some people say its easy. yes it is easy to implements but hard to figure out :)

[@Sharky-1507]

3rd

[@aashishbathe]

This was in no way a hard problem lol, if someone knows Trie then its a medium at max.

[@chaitanyasharma6270]

the first solution doesnt submit in java
class Solution {
public int[] sumPrefixScores(String[] words) {
Map map = new HashMap();
for(String w:words){
for(int i=w.length();i>=1;i--){
String sub = w.substring(0,i);
map.put(sub,map.getOrDefault(sub,0)+1);
}
}
int[] res = new int[words.length];
for(int i=0;i=1;j--){
String sub = w.substring(0,j);
c+=map.get(sub);
}
res[i]=c;
}
return res;
}
}
how does leetcode even calculate the times?!

[@AshwinRB-yi3kf]

I tried a similar approach in c++, it doesnt get accepted too. Might have to do with how different languages handle string operations, idk

[@chaitanyasharma6270]

@@AshwinRB-yi3kf or maybe they compile our codes again and again for each test case but that seems pointless

[@axelcool1234]

@@chaitanyasharma6270 I'm pretty sure the only reason the Python solution passes is due to Python being given longer time to complete due to how slow the language is. I submitted a hashmap solution in Rust, and Rust's string slicing is constant time. I still TLEd.

[@aashishbathe]

0 views xD

[@sri_harsha_dv]

9:00 did you mean to actually trie it?