Skip to content

28. Find the Index of the First Occurrence in a String

DifficultyEasy

Description

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.

Solutions

Solution 1: Traversal

Thinking

The first idea is to try every start \(i\) in \(\textit{haystack}\) and test whether the length-\(m\) slice equals \(\textit{needle}\). With \(n,m \le 10^4\), the worst case \(O((n-m)m)\) is about \(10^8\) and usually passes.

The bottleneck is paying \(m\) character comparisons at many near-matches. Smarter matchers amortize toward linear time, but this size does not force them yet.

We only need the first hit; a mismatch just moves on to the next \(i\).

So scan \(i\) from \(0\) to \(n-m\), return \(i\) on equality, else \(-1\). Extra space is \(O(1)\).

We compare the string \(\textit{needle}\) with each character of the string \(\textit{haystack}\) as the starting point. If we find a matching index, we return it directly.

Assuming the length of the string \(\textit{haystack}\) is \(n\) and the length of the string \(\textit{needle}\) is \(m\), the time complexity is \(O((n-m)m)\), and the space complexity is \(O(1)\).

1
2
3
4
5
6
7
class Solution:
    def strStr(self, haystack: str, needle: str) -> int:
        n, m = len(haystack), len(needle)
        for i in range(n - m + 1):
            if haystack[i : i + m] == needle:
                return i
        return -1
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
class Solution {
    public int strStr(String haystack, String needle) {
        int n = haystack.length(), m = needle.length();
        for (int i = 0; i + m <= n; ++i) {
            if (haystack.substring(i, i + m).equals(needle)) {
                return i;
            }
        }
        return -1;
    }
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
class Solution {
public:
    int strStr(string haystack, string needle) {
        int n = haystack.size(), m = needle.size();
        for (int i = 0; i + m <= n; ++i) {
            if (haystack.substr(i, m) == needle) {
                return i;
            }
        }
        return -1;
    }
};
1
2
3
4
5
6
7
8
9
func strStr(haystack string, needle string) int {
    n, m := len(haystack), len(needle)
    for i := 0; i <= n-m; i++ {
        if haystack[i:i+m] == needle {
            return i
        }
    }
    return -1
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
function strStr(haystack: string, needle: string): number {
    const m = haystack.length;
    const n = needle.length;
    for (let i = 0; i <= m - n; i++) {
        let isEqual = true;
        for (let j = 0; j < n; j++) {
            if (haystack[i + j] !== needle[j]) {
                isEqual = false;
                break;
            }
        }
        if (isEqual) {
            return i;
        }
    }
    return -1;
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
impl Solution {
    pub fn str_str(haystack: String, needle: String) -> i32 {
        let n = haystack.len();
        let m = needle.len();
        if m > n {
            return -1;
        }
        for i in 0..=n - m {
            if &haystack[i..i + m] == needle {
                return i as i32;
            }
        }
        -1
    }
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
/**
 * @param {string} haystack
 * @param {string} needle
 * @return {number}
 */
var strStr = function (haystack, needle) {
    const slen = haystack.length;
    const plen = needle.length;
    if (slen == plen) {
        return haystack == needle ? 0 : -1;
    }
    for (let i = 0; i <= slen - plen; i++) {
        let j;
        for (j = 0; j < plen; j++) {
            if (haystack[i + j] != needle[j]) {
                break;
            }
        }
        if (j == plen) return i;
    }
    return -1;
};
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
public class Solution {
    public int StrStr(string haystack, string needle) {
        for (var i = 0; i < haystack.Length - needle.Length + 1; ++i) {
            var j = 0;
            for (; j < needle.Length; ++j) {
                if (haystack[i + j] != needle[j]) break;
            }
            if (j == needle.Length) return i;
        }
        return -1;
    }
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
class Solution {
    /**
     * @param String $haystack
     * @param String $needle
     * @return Integer
     */
    function strStr($haystack, $needle) {
        $n = strlen($haystack);
        $m = strlen($needle);
        for ($i = 0; $i + $m <= $n; $i++) {
            if (substr($haystack, $i, $m) === $needle) {
                return $i;
            }
        }
        return -1;
    }
}

Solution 2: Rabin-Karp String Matching Algorithm

Thinking

Solution 1 may compare all \(m\) characters at every start, approaching \(O(nm)\). We want the next window to reuse work from the last one.

A fixed-length substring can be rolling-hashed: add the incoming character, drop the outgoing one, update in \(O(1)\). When the window hash equals \(\textit{needle}\)'s hash, compare the raw strings to rule out a collision.

One scan of \(\textit{haystack}\) then costs expected \(O(n+m)\).

The Rabin-Karp algorithm essentially uses a sliding window combined with a hash function to compare the hashes of fixed-length strings, which can reduce the time complexity of comparing whether two strings are the same to \(O(1)\).

Assuming the length of the string \(\textit{haystack}\) is \(n\) and the length of the string \(\textit{needle}\) is \(m\), the time complexity is \(O(n+m)\), and the space complexity is \(O(1)\).

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
class Solution:
    def strStr(self, haystack: str, needle: str) -> int:
        n, m = len(haystack), len(needle)
        mod = (1 << 31) - 1
        target = sha = 0
        multi = 1
        for i in range(m):
            target = (target * 256 + ord(needle[i])) % mod
        for _ in range(1, m):
            multi = multi * 256 % mod
        left = 0
        for right in range(n):
            sha = (sha * 256 + ord(haystack[right])) % mod
            if right - left + 1 < m:
                continue
            if sha == target and haystack[left : right + 1] == needle:
                return left
            sha = (sha - ord(haystack[left]) * multi % mod + mod) % mod
            left += 1
        return -1
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
class Solution {
    public int strStr(String haystack, String needle) {
        int n = haystack.length(), m = needle.length();
        final int mod = (1 << 31) - 1;
        long target = 0, sha = 0, multi = 1;
        for (int i = 0; i < m; ++i) {
            target = (target * 256 + needle.charAt(i)) % mod;
        }
        for (int i = 1; i < m; ++i) {
            multi = multi * 256 % mod;
        }
        int left = 0;
        for (int right = 0; right < n; ++right) {
            sha = (sha * 256 + haystack.charAt(right)) % mod;
            if (right - left + 1 < m) {
                continue;
            }
            if (sha == target && haystack.substring(left, right + 1).equals(needle)) {
                return left;
            }
            sha = (sha - haystack.charAt(left) * multi % mod + mod) % mod;
            ++left;
        }
        return -1;
    }
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
class Solution {
public:
    int strStr(string haystack, string needle) {
        int n = haystack.size(), m = needle.size();
        const long long mod = (1LL << 31) - 1;
        long long target = 0, sha = 0, multi = 1;
        for (int i = 0; i < m; ++i) {
            target = (target * 256 + needle[i]) % mod;
        }
        for (int i = 1; i < m; ++i) {
            multi = multi * 256 % mod;
        }
        int left = 0;
        for (int right = 0; right < n; ++right) {
            sha = (sha * 256 + haystack[right]) % mod;
            if (right - left + 1 < m) {
                continue;
            }
            if (sha == target && haystack.substr(left, m) == needle) {
                return left;
            }
            sha = (sha - haystack[left] * multi % mod + mod) % mod;
            ++left;
        }
        return -1;
    }
};
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
func strStr(haystack string, needle string) int {
    n, m := len(haystack), len(needle)
    sha, target, left, right, mod := 0, 0, 0, 0, 1<<31-1
    multi := 1
    for i := 0; i < m; i++ {
        target = (target*256%mod + int(needle[i])) % mod
    }
    for i := 1; i < m; i++ {
        multi = multi * 256 % mod
    }

    for ; right < n; right++ {
        sha = (sha*256%mod + int(haystack[right])) % mod
        if right-left+1 < m {
            continue
        }
        if sha == target && haystack[left:right+1] == needle {
            return left
        }
        sha = (sha - (int(haystack[left])*multi)%mod + mod) % mod
        left++
    }
    return -1
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
function strStr(haystack: string, needle: string): number {
    const n = haystack.length;
    const m = needle.length;
    const mod = 2 ** 31 - 1;
    let target = 0;
    let sha = 0;
    let multi = 1;
    for (let i = 0; i < m; ++i) {
        target = (target * 256 + needle.charCodeAt(i)) % mod;
    }
    for (let i = 1; i < m; ++i) {
        multi = (multi * 256) % mod;
    }
    let left = 0;
    for (let right = 0; right < n; ++right) {
        sha = (sha * 256 + haystack.charCodeAt(right)) % mod;
        if (right - left + 1 < m) {
            continue;
        }
        if (sha === target && haystack.slice(left, right + 1) === needle) {
            return left;
        }
        sha = (sha - ((haystack.charCodeAt(left) * multi) % mod) + mod) % mod;
        ++left;
    }
    return -1;
}

Solution 3: KMP

Thinking

Solution 2 makes a window comparison expected \(O(1)\), but it still hashes modulo a prime and must verify the raw strings on a collision. We want a worst-case linear scan without hashing.

After a mismatch we need not rewind \(\textit{haystack}\) to the start of the window. The prefix function of \(\textit{needle}\) stores the longest proper border of the matched prefix, so we know where in the pattern to resume.

Build \(\textit{next}\) for \(\textit{needle}\), then scan \(\textit{haystack}\) once, falling back only along \(\textit{next}\). Time \(O(n+m)\) and extra space \(O(m)\).

Compute the prefix function \(\textit{next}\) of \(\textit{needle}\), where \(\textit{next}[i]\) is the longest proper border of \(\textit{needle}[0..i]\). Scan \(\textit{haystack}\): equal characters grow the match length, and a mismatch jumps it to \(\textit{next}[j-1]\). When the match length reaches \(m\), return the start index \(i-m+1\).

The time complexity is \(O(n+m)\), and the space complexity is \(O(m)\), where \(n\) and \(m\) are the lengths of \(\textit{haystack}\) and \(\textit{needle}\).

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
class Solution:
    def strStr(self, haystack: str, needle: str) -> int:
        n, m = len(haystack), len(needle)
        nxt = [0] * m
        j = 0
        for i in range(1, m):
            while j and needle[i] != needle[j]:
                j = nxt[j - 1]
            if needle[i] == needle[j]:
                j += 1
            nxt[i] = j
        j = 0
        for i, ch in enumerate(haystack):
            while j and ch != needle[j]:
                j = nxt[j - 1]
            if ch == needle[j]:
                j += 1
            if j == m:
                return i - m + 1
        return -1
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
class Solution {
    public int strStr(String haystack, String needle) {
        int n = haystack.length(), m = needle.length();
        int[] nxt = new int[m];
        for (int i = 1, j = 0; i < m; ++i) {
            while (j > 0 && needle.charAt(i) != needle.charAt(j)) {
                j = nxt[j - 1];
            }
            if (needle.charAt(i) == needle.charAt(j)) {
                ++j;
            }
            nxt[i] = j;
        }
        for (int i = 0, j = 0; i < n; ++i) {
            while (j > 0 && haystack.charAt(i) != needle.charAt(j)) {
                j = nxt[j - 1];
            }
            if (haystack.charAt(i) == needle.charAt(j)) {
                ++j;
            }
            if (j == m) {
                return i - m + 1;
            }
        }
        return -1;
    }
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
class Solution {
public:
    int strStr(string haystack, string needle) {
        int n = haystack.size(), m = needle.size();
        vector<int> nxt(m);
        for (int i = 1, j = 0; i < m; ++i) {
            while (j > 0 && needle[i] != needle[j]) {
                j = nxt[j - 1];
            }
            if (needle[i] == needle[j]) {
                ++j;
            }
            nxt[i] = j;
        }
        for (int i = 0, j = 0; i < n; ++i) {
            while (j > 0 && haystack[i] != needle[j]) {
                j = nxt[j - 1];
            }
            if (haystack[i] == needle[j]) {
                ++j;
            }
            if (j == m) {
                return i - m + 1;
            }
        }
        return -1;
    }
};
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
func strStr(haystack string, needle string) int {
    n, m := len(haystack), len(needle)
    nxt := make([]int, m)
    for i, j := 1, 0; i < m; i++ {
        for j > 0 && needle[i] != needle[j] {
            j = nxt[j-1]
        }
        if needle[i] == needle[j] {
            j++
        }
        nxt[i] = j
    }
    for i, j := 0, 0; i < n; i++ {
        for j > 0 && haystack[i] != needle[j] {
            j = nxt[j-1]
        }
        if haystack[i] == needle[j] {
            j++
        }
        if j == m {
            return i - m + 1
        }
    }
    return -1
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
function strStr(haystack: string, needle: string): number {
    const n = haystack.length;
    const m = needle.length;
    const nxt = Array(m).fill(0);
    for (let i = 1, j = 0; i < m; ++i) {
        while (j > 0 && needle[i] !== needle[j]) {
            j = nxt[j - 1];
        }
        if (needle[i] === needle[j]) {
            ++j;
        }
        nxt[i] = j;
    }
    for (let i = 0, j = 0; i < n; ++i) {
        while (j > 0 && haystack[i] !== needle[j]) {
            j = nxt[j - 1];
        }
        if (haystack[i] === needle[j]) {
            ++j;
        }
        if (j === m) {
            return i - m + 1;
        }
    }
    return -1;
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
impl Solution {
    pub fn str_str(haystack: String, needle: String) -> i32 {
        let haystack = haystack.as_bytes();
        let needle = needle.as_bytes();
        let n = haystack.len();
        let m = needle.len();
        let mut nxt = vec![0; m];
        let mut j = 0;
        for i in 1..m {
            while j > 0 && needle[i] != needle[j] {
                j = nxt[j - 1];
            }
            if needle[i] == needle[j] {
                j += 1;
            }
            nxt[i] = j;
        }
        j = 0;
        for i in 0..n {
            while j > 0 && haystack[i] != needle[j] {
                j = nxt[j - 1];
            }
            if haystack[i] == needle[j] {
                j += 1;
            }
            if j == m {
                return (i + 1 - m) as i32;
            }
        }
        -1
    }
}

Comments