What is the easiest way to find the first occurrence in a string using two pointers?

Use a pointer on haystack and a pointer on needle, increment both on matches, and reset needle pointer on mismatches, returning the haystack index when needle pointer reaches its length.

How do I handle the case when needle is not present in haystack?

After scanning the entire haystack without completing a full needle match, return -1 to indicate no occurrence.

Can substring slicing replace character-by-character comparison?

Yes, checking substrings of haystack equal to needle length preserves two-pointer logic and can simplify code while maintaining correctness.

What is a common mistake when using two pointers for this problem?

A common mistake is resetting both pointers improperly, which can skip valid matches and yield incorrect first occurrence indices.

Are there more efficient algorithms for this pattern?

Yes, KMP or Rabin-Karp algorithms improve time complexity, but naive two-pointer scanning is acceptable for interviews and ensures correct first occurrence detection.

#28

Easy

auto_awesome双·指针·invariant

LeetCode 题解工作台

找出字符串中第一个匹配项的下标

给你两个字符串 haystack 和 needle ，请你在 haystack 字符串中找出 needle 字符串的第一个匹配项的下标（下标从 0 开始）。如果 needle 不是 haystack 的一部分，则返回 -1 。示例 1：输入： haystack = "sadbutsad", ne…

双指针字符串字符串匹配

题目描述

给你两个字符串 haystack 和 needle ，请你在 haystack 字符串中找出 needle 字符串的第一个匹配项的下标（下标从 0 开始）。如果 needle 不是 haystack 的一部分，则返回 -1 。

示例 1：

输入：haystack = "sadbutsad", needle = "sad"
输出：0
解释："sad" 在下标 0 和 6 处匹配。
第一个匹配项的下标是 0 ，所以返回 0 。

示例 2：

输入：haystack = "leetcode", needle = "leeto"
输出：-1
解释："leeto" 没有在 "leetcode" 中出现，所以返回 -1 。

提示：

1 <= haystack.length, needle.length <= 10⁴
haystack 和 needle 仅由小写英文字符组成

lightbulb

解题思路

方法一：遍历

以字符串 haystack 的每一个字符为起点与字符串 needle 进行比较，若发现能够匹配的索引，直接返回即可。

假设字符串 haystack 长度为 $n$ ，字符串 needle 长度为 $m$ ，则时间复杂度为 $O((n-m) \times m)$ ，空间复杂度 $O(1)$ 。

1

2

3

4

5

6

7

8

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

speed

复杂度分析

指标	值
时间	complexity is O((N-M+1)*M) in the worst case for a naive two-pointer scan, where N is haystack length and M is needle length. Space complexity is O(1) extra for pointer tracking; no additional data structures are required.
空间	Depends on the final approach

psychology

面试官常问的追问

外企场景

question_mark
Checking if candidate matches incrementally rather than full substring comparisons.
question_mark
Asking about worst-case behavior when haystack contains repeated partial matches of needle.
question_mark
Interest in whether early termination is implemented to optimize sequential scans.

warning

常见陷阱

外企场景

error
Resetting both pointers incorrectly on mismatch, skipping potential matches.
error
Assuming needle appears and not handling the -1 return properly.
error
Confusing substring lengths and causing index out-of-bounds errors during scanning.

swap_horiz

进阶变体

外企场景

arrow_right_alt
Return all indices where needle occurs instead of just the first.
arrow_right_alt
Allow wildcard characters in needle during matching.
arrow_right_alt
Implement using KMP or Rabin-Karp for improved time complexity.

help

常见问题

外企场景

继续练习

#1023 驼峰式匹配 #5 最长回文子串 #125 验证回文串