String Matching in an Array - Leetcode 1408 - Python

[@LeonLeonLeonardo]

Sometimes the brute force is the only way 😶‍🌫

[@staywithmeforever]

Because it’s easy

[@anonanon6596]

I guess this is a bug raport for your website:
In the practice section, if you set a question as solved and then change list (for example from blind 75 to 150), the question gets unchecked. It gets checked back on when you press f5.

[@anantakesharipanda4085]

Hey Navdeep! I was watching your video on Trie in your Advanced algo course yesterday to solve *Problem **#1032* , hence that’s where my first intuition went for this problem as well. But then I thought, “No way that would make this an easy problem.”

[@clementjean4905]

Another approach to consider is sorting the words by size (substring size

[@prathamesh-bhosale]

Yes that was my first thought I was honestly surprised it was better than brute force approach. One more optimization I found was to break once a match was found for words[i] it avoids going all the way to end of the array each time. Good catch on the same length words didn't really think of that!!

[@clementjean4905]

@prathamesh-bhosale the break is required I think, otherwise you could have duplicates. Did I misunderstand what you meant?

[@ListeningTheWind]

@@clementjean4905 could you tell me what is the time complexity of the approach you mentioned above

[@clementjean4905]

@@ListeningTheWind the sorting is O(N Log N) and the checking of the string should be less than O(N^2 * M). I'm not entirely sure on how to calculate that properly though. If anyone has insights on this, I'm interested.

[@ukeNlife]

Yeah. I also though of this

[@avishjain7375]

Correct me if wrong, sorting the words by size we can find if a is substring of b (a

[@staywithmeforever]

@@avishjain7375 in python it doesn't matter

[@staywithmeforever]

And still u need the indexes, the answer should be in low to high index format

[@moralized]

1:00 "maas" :D

[@NeetCodeIO]

Something something broken clock ⏰ 😂

[@Code_Leveler]

Thanks a lot sir 😁 , I tried to solve it with Rabin karp it was pretty difficult for me as i had to revise the concept to solve the problem
Here's the code => Rabin Karp
class Solution {
public final static int d=256;
public List stringMatching(String[] words) {
Set res=new HashSet();
int q=101;
for(int i=0;i

[@3thmnify]

You convert each word into a number which is the product of its letters. Then divide each word by every other word and check if modulus 0, if so compare the actual strings.
This gives you O(n) space and O(n * L) time.
The time complexity is actually slightly more, due to the possibility of collisions, but not by much. You could do some character analysis to decrease the factorization, and maintain a mapping of each character to its “reduced” number, which will take O(L) space, but reduce the number of collisions.

[@vierliu5322]

i implemented a trie extended with a special lookup function for substring, but it turns out to be less performant than the easy nested loop implementation.
Substring search on trie will visit the whole tree on a search miss, degenerating the implementation to O(n^2) 😂

[@boxicool]

Noob question. Where should i start with such exercies? I know basic syntax of python.

[@business_central]

I spent my time thinking of Trie... you can laugh at me everyone I messed up

[@flamendless]

Good trie

[@anantakesharipanda4085]

So did I, my first thought was, “How is this an easy problem?” Efficient substring search algorithms can be complicated to implement.
But implementing Trie in this problem will definitely make it a hard problem, just like *problem **#1032* .

[@floriankubiak7313]

The trie implementation is part of the editorial. It's not a mess-up - it's a good implementation for boundary conditions that have lots of lookups.

[@business_central]

​@@flamendless love this 🤣

[@business_central]

@@floriankubiak7313 oh really? I need to check that out, it was very hard and I couldn't come up with any solution

[@STACYEMMA-y2e]

Brute forced again , today's problem

[@krunalkp1032]

o(n) Solution No KMP and No Rabin Karp
combine all words by ' ' space
Now search every word count is > 1 or not
Code :
class Solution:
def stringMatching(self, words: List[str]) -> List[str]:
sentence = ' '.join(words)
answer = []
for i in words:
if sentence.count(i) > 1:
answer.append(i)
return answer

[@NeetCodeIO]

Is this actually more efficient? Doesn't it just move the complexity to the count operation which now happens over the sentence and still does the same number of comparisons?

[@krunalkp1032]

​@@NeetCodeIO It shows me 100% while leetcode submission, but I guess worst time complexity would be O(n*len(word))
My bad, word in sentence TC is O(n) in python but
word count in sentence TC is O(n*len(word))
I overlooked it.

[@codewithven9391]

@@krunalkp1032 you are counting the number of time the word appears in the entire string each time. The time complexity is the same as brute force ie O(n^2 * L^2). Just because you're getting a 100% doesn't mean the time complexity is better.

[@alizu3803]

same time complexity bro

[@santhu-hw2qw]

DONE

[@yang5843]

An easy one

[@freecourseplatformenglish2829]

Untill interviewer ask you to optimize solution. he is expecting you to use KMP or Rabin-karp algorithm.

[@JamesBond-mq7pd]

@@freecourseplatformenglish2829 Ah yes, because every good interview is just a subtle test to see if you can read their mind and whip out KMP or Rabin-Karp on cue. Who cares about problem-solving steps when you could just impress them with algorithm trivia instead. 🫡💀