28. Find the Index of the First Occurrence in a String LeetCode Solution
In this guide we will provide 28. Find the Index of the First Occurrence in a String LeetCode Solution with best time and space complexity. The solution to Find the Index of the First Occurrence in a String problem is provided in various programming languages like C++, Java and python. This will be helpful for you if you are preparing for placements, hackathon, interviews or practice purposes. The solutions provided here are very easy to follow and with detailed explanations.
Problem Statement of Find the Index of the First Occurrence in a String
Given two strings needle and haystack, return the index of the first occurrence of needle in haystack, or -1 if needle is not part of haystack.
Example 1:
Input: haystack = “sadbutsad”, needle = “sad”
Output: 0
Explanation: “sad” occurs at index 0 and 6.
The first occurrence is at index 0, so we return 0.
Example 2:
Input: haystack = “leetcode”, needle = “leeto”
Output: -1
Explanation: “leeto” did not occur in “leetcode”, so we return -1.
Constraints:
1 <= haystack.length, needle.length <= 104
haystack and needle consist of only lowercase English characters.
Complexity Analysis
Time Complexity: O((m – n)n), where m = |\texttt{haystack}| and n = |\texttt{needle}|
Space Complexity: O(1)
28. Find the Index of the First Occurrence in a String LeetCode Solution in C++
class Solution {
public:
int strStr(string haystack, string needle) {
const int m = haystack.length();
const int n = needle.length();
for (int i = 0; i < m - n + 1; i++)
if (haystack.substr(i, n) == needle)
return i;
return -1;
}
}; /* code provided by PROGIEZ */
28. Find the Index of the First Occurrence in a String LeetCode Solution in Java
class Solution {
public int strStr(String haystack, String needle) {
final int m = haystack.length();
final int n = needle.length();
for (int i = 0; i < m - n + 1; ++i)
if (haystack.substring(i, i + n).equals(needle))
return i;
return -1;
}
} // code provided by PROGIEZ
28. Find the Index of the First Occurrence in a String LeetCode Solution in Python
class Solution:
def strStr(self, haystack: str, needle: str) -> int:
m = len(haystack)
n = len(needle)
for i in range(m - n + 1):
if haystack[i:i + n] == needle:
return i
return -1 #code by PROGIEZ
