LeetCode #28 - Implement StrStr
December 14, 2020
Hello fellow devs 👋! We have a new LeetCode problem today involving string.
Problem Statement
Return the index of the first occurrence of needle in haystack, or -1 if needle is not part of haystack.
Clarification:
What should we return when needle is an empty string? This is a great question to ask during an interview.
For the purpose of this problem, we will return 0 when needle is an empty string. This is consistent to C’s strstr() and Java’s indexOf().
Constraints:
- 0 ≤
haystack.length,needle.length≤ 5 × 104 haystackandneedleconsist of only lower-case English characters.
Examples
Example 1:
Input: haystack = "hello", needle = "ll"
Output: 2Example 2:
Input: haystack = "aaaaa", needle = "bba"
Output: -1Example 3:
Input: haystack = "", needle = ""
Output: 0Analysis
This problem can be rephrased in simple words as, given two strings haystack and needle. Find if needle is present in the haystack. We can easily do it by using library methods but since this is an algorithmic problem, we should not do it.
Plus, Implement StrStr is a stupid name for this problem (sorry C lovers 😛). If I were the mighty owner of the LeetCode, I would name it Find Needle In A Haystack 😄.
If the needle is present in the haystack, return its starting index, else return -1.
Approach
We will follow the below steps —
!. Take the length of the needle as needleLength.
- Scan the
haystackfrom left to right. - Check if substrings of length
needleLengthare present in it.
Time Complexity
The string is traversed once so the time complexity will be O(n).
Space Complexity
We may have to create n substrings of length 1 each, therefore, the space complexity will also be O(n).
Code
Java
public class ImplementStrStr {
public int strStr(String haystack, String needle) {
// Base condition
if (haystack == null || needle == null) {
return -1;
}
// Special case
if (haystack.equals(needle)) {
return 0;
}
// length of the needle
int needleLength = needle.length();
// Loop through the haystack and slide the window
for (int i = 0; i < haystack.length() - needleLength + 1; i++) {
// Check if the substring equals to the needle
if (haystack.substring(i, i + needleLength).equals(needle)) {
return i;
}
}
return -1;
}
}Python
class ImplementStrStr:
def strStr(haystack: str, needle: str) -> int:
# Base conditions
if haystack is None or needle is None:
return -1
# Special case
if haystack == needle:
return 0
# Length of the needle
needleLength = len(needle)
# Loop through the haystack and slide the window
for i in range(len(haystack) - needleLength + 1):
if haystack[i:i + needleLength] == needle:
return i
return -1JavaScript
var strStr = function (haystack, needle) {
// Base condition
if (haystack == null || needle == null) {
return -1;
}
// Special case
if (haystack === needle) {
return 0;
}
// length of the needle
const needleLength = needle.length;
// Loop through the haystack and slide the window
for (let i = 0; i < haystack.length - needleLength + 1; i++) {
// Check if the substring equals to the needle
if (haystack.substring(i, i + needleLength) === needle) {
return i;
}
}
return -1;
};Kotlin
class ImplementStrStr {
fun strStr(haystack: String, needle: String): Int {
// Special case
if (haystack == needle) {
return 0
}
// length of the needle
val needleLength = needle.length
// Loop through the haystack and slide the window
for (i in 0 until haystack.length - needleLength + 1) {
// Check if the substring equals to the needle
if (haystack.substring(i, i + needleLength) == needle) {
return i
}
}
return -1
}
}Complete Code
Conclusion
Congratulations 👏! We have solved yet another problem from LeetCode involving string.
I hope you enjoyed this post. Feel free to share your thoughts on this.
You can find the complete source code on my GitHub repository. If you like what you learn, feel free to fork 🔪 and star ⭐ it.
Till next time… Happy coding 😄 and Namaste 🙏!
