Example 13
实现 strStr()
题目概述：给你两个字符串haystack 和 needle ，请你在 haystack 字符串中找出 needle 字符串出现的第一个位置（下标从 0 开始）。如果不存在，则返回 -1 。
说明：
当needle是空字符串时，我们应当返回什么值呢？这是一个在面试中很好的问题。
对于本题而言，当needle是空字符串时我们应当返回 0 。这与 C 语言的strstr()以及 Java 的indexOf()定义相符。
示例 1：
输入：haystack = "hello", needle = "ll"
输出：2
示例 2：
输入：haystack = "aaaaa", needle = "bba"
输出：-1
解题思路：让字符串needle（长度为m） 与字符串haystack 的所有长度为m 的子串均匹配一次。
如果当前子串匹配成功，我们返回当前子串的开始位置即可，如果所有子串都匹配失败，则返回−1。
解题步骤：
1. 定义变量needleLength与haystackLength分别记录两个字符串的长度。
2. 依次遍历haystack字符串中自0索引至haystackLength - needleLength索引为开始位置的长度为needleLength的字符串，若与needle相等，则将该索引返回，否则继续考察。
3. 遍历结束，说明没有符合条件的子串，则返回-1。
示例代码如下：
public class ImplementStrStr { /** * 实现strStr()函数。 * 给你两个字符串haystack 和 needle ，请你在 haystack 字符串中找出 needle 字符串出现的第一个位置（下标从 0 开始）。如果不存在，则返回 -1 。 * 说明： * 当needle是空字符串时，我们应当返回什么值呢？这是一个在面试中很好的问题。 * 对于本题而言，当needle是空字符串时我们应当返回 0 。这与 C 语言的strstr()以及 Java 的indexOf()定义相符。 * 示例 1： * 输入：haystack = "hello", needle = "ll" * 输出：2 * 示例 2： * 输入：haystack = "aaaaa", needle = "bba" * 输出：-1 * 来源：力扣（LeetCode） * 链接：https://leetcode.cn/problems/implement-strstr */ public static void main(String[] args) { ImplementStrStr iss = new ImplementStrStr(); System.out.println(iss.strStr("hello", "ll")); // 2 } /** * 网友 * @param haystack * @param needle * @return */ /*public int strStr(String haystack, String needle) { return haystack.indexOf(needle); }*/ /** * 个人 * * @param haystack * @param needle * @return */ public int strStr(String haystack, String needle) { int needleLength = needle.length(); int haystackLength = haystack.length(); for (int i = 0; i <= haystackLength - needleLength; i++) { if (haystack.substring(i, i + needleLength).equals(needle)) return i; } return -1; } /** * 官方 * @param haystack * @param needle * @return */ /*public int strStr(String haystack, String needle) { int n = haystack.length(), m = needle.length(); for (int i = 0; i + m <= n; i++) { boolean flag = true; for (int j = 0; j < m; j++) { if (haystack.charAt(i + j) != needle.charAt(j)) { flag = false; break; } } if (flag) { return i; } } return -1; }*/ }
