String Matching in an Array - Leetcode 1408 - Python

0:00 - Read the problem
0:30 - Drawing Explanation
1:47 - Coding Explanation
4:55 - Pattern Matching Explanation
7:26 - Recommended videos


leetcode 1408

#neetcode #leetcode #python

[LeonLeonLeonardo]

Sometimes the brute force is the only way 😶‍🌫

[anonanon]

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.

[anantakesharipanda]

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

[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<String> stringMatching(String[] words) {
Set<String> res=new HashSet<>();
int q=101;
for(int i=0;i<words.length;i++)
{
String word=words[i];
for(int j=0;j<words.length;j++)
{
if(i!=j&&search(word, words[j], q))
{
res.add(word);
break;
}
}
}
return new ArrayList<>(res);
}
private static boolean search(String pat, String txt, int q)
{
int m=pat.length();
int n=txt.length();
if(n<m)
{
return false;
}
int p=0;
int t=0;
int h=1;
for(int i=0;i<m-1;i++)
{
h=(h*d)%q;
}
for(int i=0;i<m;i++)
{
p=(d*p+pat.charAt(i))%q;
t=(d*t+txt.charAt(i))%q;
}
for(int i=0;i<=n-m;i++)
{
if(p==t)
{
int j;
for(j=0;j<m;j++)
{

{
break;
}
}
if(j==m)
{
return true;
}
}
if(i<n-m)
{

if(t<0)
{
t=t+q;
}
}
}
return false;
}
}

[clementjean]

Another approach to consider is sorting the words by size (substring size <= word size). This let you start the inner loop with j = i + 1 as mentioned in the brute force solution. On top of that, you can skip all the words that have the same length as words[i] because the constraints say that all the words are unique.

[avishjain]

Correct me if wrong, sorting the words by size we can find if a is substring of b (a<b) in liner time which essentially gives us O(n^2*L)

[thmnify]

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.

[vierliu]

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

[krunalkp]

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

[boxicool]

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

[STACYEMMA-ye]

Brute forced again, today's problem

[business_central]

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