In the Leetcode Find the Index of the First Occurrence in a String problem solution 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.
Solution in C Programming
int strStr(char* haystack, char* needle){
/*
Get string length infromation, and intialze the comaprion index for KMP alogorithm.
*/
int lens = strlen(haystack);
int lenn = strlen(needle);
int ps = 0; int pn = 0;
/*
Comfirm the length of needle.
Avoid the problem that the ffs array cannot be declared when the length is 0.
*/
if(!lenn) return 0;
/*
Declare an integer array "ffs" with the same length as needle.
This will be used for storage the fuilure value of each needle character.
*/
int ffs[lenn];
/*
The following is the calculation logic of failure fuction.
Declare an integer "curpre" to record the current failure value.
*/
ffs[0] = -1;
for(int i = 1; i < lenn; i++){
int curpre = ffs[i - 1];
while((needle[i] != needle[curpre + 1]) && (curpre >= 0))
curpre = ffs[curpre];
if(needle[i] == needle[curpre + 1])
ffs[i] = curpre + 1;
else ffs[i] = -1;
}
/*
The folling is the KMP alogorithm.
*/
while((ps < lens) && (pn < lenn)){
if(needle[pn] == haystack[ps]){
pn++; ps++;
}
else{
if(pn == 0)
ps++;
else
pn = ffs[pn - 1] + 1;
}
}
if(pn < lenn) return -1;
else return ps - lenn;
}Solution in C++ Programming
class Solution {
public:
int strStr(string main, string sub) {
if (sub.empty()) {
return 0;
}
int mainHash = getHash(main.substr(0, sub.size()));
int subHash = getHash(sub);
int size = main.size() - sub.size() + 1;
for (int i = 0; i < size; ++i) {
if (mainHash == subHash) {
if (sub == main.substr(i, sub.size())) {
return i;
}
}else {
mainHash -= main[i] - '0';
mainHash += main[i + sub.size()] - '0';
}
}
return -1;
}
private:
int getHash(const string& str) {
int res = 0;
for (const auto c : str) {
res += c - '0';
}
return res;
}
};Solution in Java Programming
class Solution {
public int strStr(String haystack, String needle) {
if(haystack == null || needle == null){
return -1;
}
if(needle.length() == 0){
return 0;
}
for(int i = 0; i < haystack.length(); i++){
if(haystack.charAt(i) == needle.charAt(0) && i + needle.length() <= haystack.length()
&& haystack.substring(i, i+needle.length()).equals(needle)){
return i;
}
}
return -1;
}
}Solution in Python Programming
class Solution(object):
def strStr(self, haystack, needle):
index = -1
i = j = 0
if(len(needle) == 0):
return 0
while(i < len(haystack) and j <len(needle)):
if (haystack[i] != needle[j]):
if (index != -1):
i = index
index = -1
j = 0
else:
if (j == 0):
index = i
j += 1
i += 1
if (j == len(needle)):
return index
else:
return -1Solution in C# Programming
public class Solution {
public int StrStr(string haystack, string needle) {
//first find indexes of first char of needle in haystack
if (!haystack.Contains(needle))
return -1;
List<int> arr = new List<int>();
for(int i= 0;i<haystack.Length;i++)
{
if(needle[0] == haystack[i])
{
arr.Add(i);
}
}
//
//Check if each indexes on arr matches the string needle
int index = -1;
for(int i=0;i<arr.Count;i++)
{
index = arr[i];
if(index > haystack.Length-needle.Length)
{
break;
}
else if(haystack.Substring(index,needle.Length) == needle)
{
return index;
}
}
return -1;
}
}Also read,