Algorithm
Problem Name: 28. Find the Index of the First Occurrence in a String
Problem Link: https://leetcode.com/problems/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 <= 104haystackandneedleconsist of only lowercase English characters.
Code Examples
#1 Code Example with C Programming
Code -
C Programming
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
void getNext(char* pattern, int* next) {
if (pattern == NULL || next == NULL) return;
int m = strlen(pattern);
int i, j;
next[0] = 0;
j = 0;
for (i = 1; i < m; i++) {
while (j > 0 && pattern[i] != pattern[j])
j = next[j - 1];
if (pattern[i] == pattern[j]) j++;
next[i] = j;
}
}
int strStr(char* haystack, char* needle) {
if (haystack == NULL || needle == NULL) return 0;
int n = strlen(haystack);
int m = strlen(needle);
if (m == 0) return 0;
int *next = (int *)calloc(m, sizeof(int));
getNext(needle, next);
int ans = -1;
int i, j;
j = 0;
for (i = 0; i < n; i++) {
while (j > 0 && haystack[i] != needle[j])
j = next[j - 1];
if (haystack[i] == needle[j]) j++;
if (j == m) {
ans = i + 1 - j;
break; /* if you want to continue search, comment out break */
j = next[j - 1];
}
}
free(next);
return ans;
}
/* Brute force */
int strStr0(char* haystack, char* needle) {
if (haystack == NULL || needle == NULL) return 0;
int n = strlen(haystack);
int m = strlen(needle);
if (m == 0) return 0;
int ans = -1;
int i, j;
j = 0;
for (i = 0; i < n; i++) {
while (j > 0 && haystack[i] != needle[j]) {
i = i + 1 - j;
j = 0;
}
if (haystack[i] == needle[j]) j++;
if (j == m) {
ans = i + 1 - j;
break; /* if you want to continue search, comment out break */
j = 0;
}
}
return ans;
}
int main() {
char str[] = "abcdacabcdabdeabcdabd";
char pattern[] = "abcdabd";
/* 6 */
printf("%d\n", strStr(str, pattern));
/* 0 */
printf("%d\n", strStr("", ""));
/* 0 */
printf("%d\n", strStr("1", ""));
return 0;
}
Input
haystack = "sadbutsad", needle = "sad"
#2 Code Example with C++ Programming
Code -
C++ Programming
class Solution {
public:
int strStr(string haystack, string needle) {
if (needle.size() == 0) return 0;
for (int i = 0; i < haystack.size(); i++)
if (haystack[i] == needle[0] && isEqual(haystack.substr(i), needle)) return i;
return -1;
}
bool isEqual(string s1, string s2) {
if (s1.size() < s2.size()) return false;
for (int i = 0; i < s2.size(); i++)
if (s1[i] != s2[i]) return false;
return true;
}
};
Input
haystack = "leetcode", needle = "leeto"
Output
-1
#3 Code Example with Javascript Programming
Code -
Javascript Programming
const strStr = function(a, b) {
if(b === '') return 0
if(a.length < b.length) return -1
if(a.length === b.length) return a === b ? 0 : -1
const m = a.length, n = b.length
const fail = Array(n).fill(-1)
// DFA
for(let i = 1; i < n; i++) {
let j = fail[i - 1]
while(j !== -1 && b[j + 1] !== b[i]) {
j = fail[j]
}
if(b[j + 1] === b[i]) fail[i] = j + 1
}
let pos = -1
for(let i = 0; i < m; i++) {
while(pos !== -1 && a[i] !== b[pos + 1]) pos = fail[pos]
if(a[i] === b[pos + 1]) {
pos++
if(pos === n - 1> return i - n + 1
}
}
return -1
};
Input
haystack = "sadbutsad", needle = "sad"
#4 Code Example with Python Programming
Code -
Python Programming
class Solution:
def strStr(self, haystack, needle):
return haystack.find(needle)
Input
haystack = "leetcode", needle = "leeto"
Output
-1
#5 Code Example with C# Programming
Code -
C# Programming
namespace LeetCode
{
public class _028_ImplementStrStr
{
public int StrStr(string haystack, string needle)
{
var needleLength = needle.Length;
if (needleLength == 0) { return 0; }
var loopLenght = haystack.Length - needleLength + 1;
var needleIndex = 0;
var n = 0;
for (int i = 0; i < loopLenght; i++)
{
needleIndex = n = 0;
while (needleIndex < needleLength
&& haystack[i + needleIndex] == needle[needleIndex])
{
if (n == 0 && needle[needleIndex] == needle[0])
{
n = needleIndex;
}
needleIndex++;
}
if (needleIndex == needleLength)
{
return i;
}
if (n > 0) i += n - 1;
}
return -1;
}
}
}
Input
haystack = "sadbutsad", needle = "sad"