Find the Index of the First Occurrence in a String Leetcode Solution
Index Of the first Occurrence Leetcode Problem :
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.
The first occurrence is at index 0, so we return 0.
Index Of First Occurrence Leetcode Solution :
Constraints :
- 1 <= haystack.length, needle.length <= 104
- haystack and needle consist of only lowercase English characters.
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.
In the “3 sum” problem you are given an integer array nums, the goal is to find all unique triplets within the array such that the sum of the elements in each triplet is equal to zero (i.e.,nums[i] + nums[j] + nums[k] == 0), and the indices i, j, and k are all distinct (i.e., i != j, i != k, and j != k).
Here are the key points for the given constraints and examples:
Constraints:
- The length of the nums array is between 3 and 3000.
- The values in the nums array can range from -100,000 to 100,000.
Approach :
Two Pointer approach:
- Initialize 2 pointers i and j, store starting index of i in ind.
- While haystack[i] and needle[j] are equal increament the i and j both pointer.
- if j has traversed all the needle string, so return the starting index of i, where you started.
- else again intialize j with 0, to traverse the string needle again.
- Update the i pointer with ind + 1.
- Repeat the steps from 2, if didn’t get the ans in previous step.
- return -1, after checking all the possibilities, out of the loop.
- End.
Prime Course Trailer
Related Banners
Get PrepInsta Prime & get Access to all 200+ courses offered by PrepInsta in One Subscription
Code :
class Solution {
public:
int strStr(string haystack, string needle) {
int h = haystack.size();
int n = needle.size();
int i=0, j=0, ind=0
;
while(i=n) return ind;
else j = 0;
i = ind+1;
}
return -1;
}
}; public class Solution {
public int strStr(String haystack, String needle) {
int h = haystack.length();
int n = needle.length();
int i = 0, j = 0, ind = 0;
while (i < h && j < n) {
ind = i;
while (i < h && j < n && haystack.charAt(i) == needle.charAt(j)) {
i++;
j++;
}
if (j >= n) return ind;
else {
j = 0;
i = ind + 1;
}
}
return -1;
}
}
class Solution:
def strStr(self, haystack: str, needle: str) -> int:
h = len(haystack)
n = len(needle)
i, j, ind = 0, 0, 0
while i < h and j < n:
ind = i
while i < h and j < n and haystack[i] == needle[j]:
i += 1
j += 1
if j >= n:
return ind
else:
j = 0
i = ind + 1
return -1
Login/Signup to comment