数据结构与算法►力扣

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

题目描述

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

示例 1：

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

示例 2：

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

提示：

  • 1 <= haystack.length, needle.length <= 104

  • haystack 和 needle 仅由小写英文字符组成

题解

最基础的解法就是文本串（haystack）和模式串needle左对齐，注意比较，如果整个模式串跟主串比较后发现不匹配，则模式串向后移动一位，继续比较。

暴力算法

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
class Solution {
    public int strStr(String haystack, String needle) {
        int N = haystack.length();
        int M = needle.length();
        for (int i = 0; i <= N - M; i++) {
            int j = 0;
            for (; j < M; j++) {
                if (needle.charAt(j) != haystack.charAt(i + j)) {
                    break;
                }
            }
            if (j == M) {
                return i;
            }
        }
        return -1;
    }
}

提交：

提交结果