String Matching in an Array - Leetcode 1408 - Python

NeetCodeIO · Intermediate ·⚡ Algorithms & Data Structures ·1y ago

Key Takeaways

The video discusses the String Matching in an Array problem on Leetcode 1408, providing a Brute Force solution and introducing the Rabin-Carp algorithm, while also comparing it to the KMP algorithm in terms of efficiency and complexity.

Full Transcript

hey everyone welcome back and let's write some more neat code today so today let's solve the problem string matching in an array it's a pretty easy problem but there are a couple more complicated solutions to this one so first let me just kind of read through the description which is we're given a list of strings and basically what we want to do is filter this list of strings such that the output list of strings for every single one of these words it shows up as a substring of a different word so for example we'd go through every word in the input and check do we want to include this one in the output we would determine that by checking is this a substring of this word no it's not is it a substring of this word nope is it a substring of this word no so we do not include this one what about this guy well we would check every other word is it a substring of the previous word you can't really see it anymore but it was mass and yes if you look at the last two characters they match this so we don't really even have to go through the rest of these we already know that this is going to be included in the output and we would do that for every other word so hero we can already see that it's a substring of this word so this will be included in the output superhero it's not a substring of any other word so we do not include it and thus this is the output this is pretty trivial to code up in most languages in Python it's very very trivial because you don't even have to do the the substring comparison like in a Brute Force kind of way you would check like the first four characters do they match this no what about the next four etc etc and that's what's going on kind of under the hood so let me just show you what the code would look like and then we'll get into the time complexity of this Brute Force solution we want to go through every word but the way I'm going to do this is like this I'm going to have the index first and I'm going to go through every single index in this list of words and let me first also declare my result which is going to be the list of the output words that's what we're going to return and now for the current word this is like our candidate and now I want to check every other word I'm going to do for J in range length of words the reason I can't do this like I can't start at I plus one and check only the words to the right of this one is kind of for obvious reasons in the drawing explanation we do have to check every other word even the words that came before this one but we definitely don't want to compare the I word with itself because every word is technically a substring of itself so we want to avoid that comparison so that's why I'm going to go through every other word but I'm going to skip the case where I is equal to J in that case we can just continue to the next iteration otherwise we want to do the comparison we want to check if the word at index I is a substring of the word at index J and python makes it easy we can just do the in operator is this string in this other string and if it is we can then once again continue or actually not even continue we can break out of the loop we can stop the inner loop because we already know that this word is going to be included and before we break we should do this result. append current word so this is the Brute Force solution let me run it now it does work pretty efficiently you can see and that's mainly due to the constraints of the problem we're going to be dealing with relatively small strings and a small set of words uh but in terms of Big O time complexity first you can see we're going through every word so let's say the length of that array is n and then we're going through every word like again so nested loops and squared this part is kind of more interesting to analyze so imagine if like our pattern was something like this a BC and then we have like some really long string just random we would do something like this compare this substring to these characters and then the next three characters etc etc that's kind of what this is doing under the hood so it's like the length of the pattern times the length of the other string if you want to like oversimplify it I guess you could just take like the length of the word and then say well this operation is then in that case L squared cuz the comparison itself is going to be proportional to the length of the string and how many times we're going to do that comparison is also kind of proportional to the length of the other string so that's where I'm getting that term from so this is the Brute Force solution it is possible actually to improve the overall time complexity though the actual runtime given the current constraints is going to be worse I think let me briefly talk about those two algorithms that we could use I'm not going to cover them in this video because they're kind of difficult especially for an easy problem and I've already recorded I think pretty good videos covering those two algorithms which I'll mention in just a second there are two textbook algorithms that are specifically designed to solve a problem like this the two are km pattern matching and then the other one is Rabin carp I don't know if I'm saying that correctly the rolling hash algorithm it's also very suited for this problem if I was going to recommend one of these to you I would one million per do this one it is conceptually so much easier to understand but even then this is a difficult algorithm I think for a medium problem even then this is considered a pretty difficult algorithm like it's kind of ordering like a hard algorithm and KMP in my opinion is just very very complicated I do have a pretty good video for that but honestly I would recommend you learn this one down here I'm not going to be covering these in this video but just to briefly explain how Rabin carp algorithm works it would kind of convert the pattern so like if this string we're trying to check if it's a substring of any of these we would convert this into a hash an integer where each of the spots so like m is going to be a number from 0 through 25 depending on like which character it is and so if we can convert that thing into an integer and like here let's say we had something like 10 I'm just making these up and then here we have zero and then here we have like 20 and then 20 this will form some integer and then uh if we were comparing it to this we would get the first four characters here get that into an integer and then we could just do an integer comparison which is more efficient than a string comparison then if we wanted to update that and just slide that window sort of to the right we would do that by getting rid of the integer here and then adding that integer there so it would just be a more efficient operation and so doing it that way you can see that the time complexity would still be a N squared because we're still having to compare every uh word to every other word but then if the comparison itself is a constant time operation well how many times are we going to do that comparison in that case it still might be proportional to the length of this string so we might do it once twice three times etc etc so the time complexity would then be n^2 times the length of the word it also of course takes that to convert this into an integer as well so the time complext would be more efficient in terms of Big O of n but it wouldn't actually be more efficient with the real runtime if you want to learn these two algorithms specifically this one let me show you how you can do so just go to YouTube and search for uh neat code and then KMP and then you'll find this video made like 3 years ago the other one just search for neat code and then search for Rabin carp and then you'll find this video about 22 minutes long but I would definitely say this one is more easy than the other one this one is 35 minutes and even just watching this once I bet you won't understand it to be honest it took me a lot longer than 35 minutes to understand this algorithm anyways if you found this helpful check out n code. for a lot more and I'll see you soon

Original Description

🚀 https://neetcode.io/ - A better way to prepare for Coding Interviews 🧑‍💼 LinkedIn: https://www.linkedin.com/in/navdeep-singh-3aaa14161/ 🐦 Twitter: https://twitter.com/neetcode1 ⭐ BLIND-75 PLAYLIST: https://www.youtube.com/watch?v=KLlXCFG5TnA&list=PLot-Xpze53ldVwtstag2TL4HQhAnC8ATf Problem Link: https://leetcode.com/problems/string-matching-in-an-array/description/ 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
Watch on YouTube ↗ (saves to browser)
Sign in to unlock AI tutor explanation · ⚡30

Playlist

Uploads from NeetCodeIO · NeetCodeIO · 0 of 60

← Previous Next →
1 Leetcode 149 - Maximum Points on a Line - Python
Leetcode 149 - Maximum Points on a Line - Python
NeetCodeIO
 2 Design Linked List - Leetcode 707 - Python
Design Linked List - Leetcode 707 - Python
NeetCodeIO
 3 Minimum Time to Collect All Apples in a Tree - Leetcode 1443 - Python
Minimum Time to Collect All Apples in a Tree - Leetcode 1443 - Python
NeetCodeIO
 4 Design Browser History - Leetcode 1472 - Python
Design Browser History - Leetcode 1472 - Python
NeetCodeIO
 5 Number of Good Paths - Leetcode 2421 - Python
Number of Good Paths - Leetcode 2421 - Python
NeetCodeIO
 6 Flip String to Monotone Increasing - Leetcode 926 - Python
Flip String to Monotone Increasing - Leetcode 926 - Python
NeetCodeIO
 7 Maximum Sum Circular Subarray - Leetcode 918 - Python
Maximum Sum Circular Subarray - Leetcode 918 - Python
NeetCodeIO
 8 Find Closest Node to Given Two Nodes - Leetcode 2359 - Python
Find Closest Node to Given Two Nodes - Leetcode 2359 - Python
NeetCodeIO
 9 Concatenated Words - Leetcode 472 - Python
Concatenated Words - Leetcode 472 - Python
NeetCodeIO
 10 Data Stream as Disjoint Intervals - Leetcode 352 - Python
Data Stream as Disjoint Intervals - Leetcode 352 - Python
NeetCodeIO
 11 LFU Cache - Leetcode 460 - Python
LFU Cache - Leetcode 460 - Python
NeetCodeIO
 12 N-th Tribonacci Number - Leetcode 1137
N-th Tribonacci Number - Leetcode 1137
NeetCodeIO
 13 Best Team with no Conflicts - Leetcode 1626 - Python
Best Team with no Conflicts - Leetcode 1626 - Python
NeetCodeIO
 14 Greatest Common Divisor of Strings - Leetcode 1071 - Python
Greatest Common Divisor of Strings - Leetcode 1071 - Python
NeetCodeIO
 15 Shortest Path in a Binary Matrix - Leetcode 1091 - Python
Shortest Path in a Binary Matrix - Leetcode 1091 - Python
NeetCodeIO
 16 Insert into a Binary Search Tree - Leetcode 701 - Python
Insert into a Binary Search Tree - Leetcode 701 - Python
NeetCodeIO
 17 Delete Node in a BST - Leetcode 450 - Python
Delete Node in a BST - Leetcode 450 - Python
NeetCodeIO
 18 Shuffle the Array (Constant Space) - Leetcode 1470 - Python
Shuffle the Array (Constant Space) - Leetcode 1470 - Python
NeetCodeIO
 19 Fruits into Basket - Leetcode 904 - Python
Fruits into Basket - Leetcode 904 - Python
NeetCodeIO
 20 Number of Subarrays of size K and Average Greater than or Equal to Threshold - Leetcode 1343 Python
Number of Subarrays of size K and Average Greater than or Equal to Threshold - Leetcode 1343 Python
NeetCodeIO
 21 Naming a Company - Leetcode 2306 - Python
Naming a Company - Leetcode 2306 - Python
NeetCodeIO
 22 As Far from Land as Possible - Leetcode 1162 - Python
As Far from Land as Possible - Leetcode 1162 - Python
NeetCodeIO
 23 Shortest Path with Alternating Colors - Leetcode 1129 - Python
Shortest Path with Alternating Colors - Leetcode 1129 - Python
NeetCodeIO
 24 Minimum Fuel Cost to Report to the Capital - Leetcode 2477 - Python
Minimum Fuel Cost to Report to the Capital - Leetcode 2477 - Python
NeetCodeIO
 25 Count Odd Numbers in an Interval Range - Leetcode 1523 - Python
Count Odd Numbers in an Interval Range - Leetcode 1523 - Python
NeetCodeIO
 26 Contains Duplicate II - Leetcode 219 - Python
Contains Duplicate II - Leetcode 219 - Python
NeetCodeIO
 27 Path with Maximum Probability - Leetcode 1514 - Python
Path with Maximum Probability - Leetcode 1514 - Python
NeetCodeIO
 28 Add to Array-Form of Integer - Leetcode 989 - Python
Add to Array-Form of Integer - Leetcode 989 - Python
NeetCodeIO
 29 Unique Paths II - Leetcode 63 - Python
Unique Paths II - Leetcode 63 - Python
NeetCodeIO
 30 Minimum Distance between BST Nodes - Leetcode 783 - Python
Minimum Distance between BST Nodes - Leetcode 783 - Python
NeetCodeIO
 31 Design Hashmap - Leetcode 706 - Python
Design Hashmap - Leetcode 706 - Python
NeetCodeIO
 32 Range Sum Query Immutable - Leetcode 303 - Python
Range Sum Query Immutable - Leetcode 303 - Python
NeetCodeIO
 33 Binary Tree Zigzag Level Order Traversal - Leetcode 103 - Python
Binary Tree Zigzag Level Order Traversal - Leetcode 103 - Python
NeetCodeIO
 34 Middle of the Linked List - Leetcode 876 - Python
Middle of the Linked List - Leetcode 876 - Python
NeetCodeIO
 35 Course Schedule IV - Leetcode 1462 - Python
Course Schedule IV - Leetcode 1462 - Python
NeetCodeIO
 36 Single Element in a Sorted Array - Leetcode 540 - Python
Single Element in a Sorted Array - Leetcode 540 - Python
NeetCodeIO
 37 Capacity to Ship Packages - Leetcode 1011 - Python
Capacity to Ship Packages - Leetcode 1011 - Python
NeetCodeIO
 38 IPO - Leetcode 502 - Python
IPO - Leetcode 502 - Python
NeetCodeIO
 39 Minimize Deviation in Array - Leetcode 1675 - Python
Minimize Deviation in Array - Leetcode 1675 - Python
NeetCodeIO
 40 Longest Turbulent Array - Leetcode 978 - Python
Longest Turbulent Array - Leetcode 978 - Python
NeetCodeIO
 41 Last Stone Weight II - Leetcode 1049 - Python
Last Stone Weight II - Leetcode 1049 - Python
NeetCodeIO
 42 Construct Quad Tree - Leetcode 427 - Python
Construct Quad Tree - Leetcode 427 - Python
NeetCodeIO
 43 Find Duplicate Subtrees - Leetcode 652 - Python
Find Duplicate Subtrees - Leetcode 652 - Python
NeetCodeIO
 44 Sort an Array - Leetcode 912 - Python
Sort an Array - Leetcode 912 - Python
NeetCodeIO
 45 Ones and Zeroes - Leetcode 474 - Python
Ones and Zeroes - Leetcode 474 - Python
NeetCodeIO
 46 Remove Duplicates from Sorted Array II - Leetcode 80 - Python
Remove Duplicates from Sorted Array II - Leetcode 80 - Python
NeetCodeIO
 47 Maximum Twin Sum of a Linked List - Leetcode 2130 - Python
Maximum Twin Sum of a Linked List - Leetcode 2130 - Python
NeetCodeIO
 48 Concatenation of Array - Leetcode 1929 - Python
Concatenation of Array - Leetcode 1929 - Python
NeetCodeIO
 49 Symmetric Tree - Leetcode 101 - Python
Symmetric Tree - Leetcode 101 - Python
NeetCodeIO
 50 Check Completeness of a Binary Tree - Leetcode 958 - Python
Check Completeness of a Binary Tree - Leetcode 958 - Python
NeetCodeIO
 51 Construct Binary Tree from Inorder and Postorder Traversal - Leetcode 106 - Python
Construct Binary Tree from Inorder and Postorder Traversal - Leetcode 106 - Python
NeetCodeIO
 52 Find Peak Element - Leetcode 162 - Python
Find Peak Element - Leetcode 162 - Python
NeetCodeIO
 53 Accounts Merge - Leetcode 721 - Python
Accounts Merge - Leetcode 721 - Python
NeetCodeIO
 54 Binary Tree Preorder Traversal (Iterative) - Leetcode 144 - Python
Binary Tree Preorder Traversal (Iterative) - Leetcode 144 - Python
NeetCodeIO
 55 Binary Tree Postorder Traversal (Iterative) - Leetcode 145 - Python
Binary Tree Postorder Traversal (Iterative) - Leetcode 145 - Python
NeetCodeIO
 56 Number of Zero-Filled Subarrays - Leetcode 2348 - Python
Number of Zero-Filled Subarrays - Leetcode 2348 - Python
NeetCodeIO
 57 Minimum Score of a Path Between Two Cities - Leetcode 2492 - Python
Minimum Score of a Path Between Two Cities - Leetcode 2492 - Python
NeetCodeIO
 58 Sqrt(x) - Leetcode 69 - Python
Sqrt(x) - Leetcode 69 - Python
NeetCodeIO
 59 Successful Pairs of Spells and Potions - Leetcode 2300 - Python
Successful Pairs of Spells and Potions - Leetcode 2300 - Python
NeetCodeIO
 60 Optimal Partition of String - Leetcode 2405 - Python
Optimal Partition of String - Leetcode 2405 - Python
NeetCodeIO

The video teaches how to solve the String Matching in an Array problem on Leetcode 1408 using a Brute Force solution and introduces the Rabin-Carp algorithm, while also comparing it to the KMP algorithm. It provides a comprehensive analysis of time complexity and algorithmic efficiency, making it a valuable resource for coding interviews.

Key Takeaways
  1. Declare a result list
  2. Go through every word in the input list
  3. Check if current word is a substring of every other word
  4. Use 'in' operator for substring comparison
  5. Append current word to result list if it is a substring of another word
  6. Analyze time complexity of the Brute Force solution
  7. Consider using the Rabin-Carp or KMP algorithm for more efficient solutions
💡 The KMP algorithm is more efficient than the Rabin-Carp algorithm for string matching problems, especially when considering the time complexity of converting strings to integers.

Related AI Lessons

⚡
Bloom Filters, Explained Properly
Learn how Bloom filters work and their benefits, including tiny memory and blazing speed, in exchange for potential false positives.
Dev.to · Daksh Gargas
 ⚡
Prefix Sums: The Preprocessing Trick That Makes Range Queries Instant
Learn how prefix sums enable instant range queries in arrays, boosting performance in various applications
Medium · Programming
 ⚡
I Thought I Was Ready for the Interview — Then One Simple Math Question Destroyed Me
A simple math question can destroy a developer's interview, highlighting the importance of being prepared for unexpected questions
Medium · Programming
 ⚡
Week 2(Day 10): LeetCode Two Pointers(slow & fast): Remove Duplicates from Sorted Array (Brute…
Learn to remove duplicates from a sorted array using the two pointers technique, improving from brute force to optimized solutions
Medium · Python

Chapters (5)

Read the problem
0:30 Drawing Explanation
1:47 Coding Explanation
4:55 Pattern Matching Explanation
7:26 Recommended videos
Up next
Stump Grinder Carbide Wheel Grinds Hardwood To Chips
Innoforge Studio
Watch →