LeetCode-28 实现strStr()
> 题目：28. 实现strStr()
> 难度：简单
> 分类：字符串
> 解决方案：双指针
今天我们学习第28题实现strStr()，这个题目是一个典型的字符串匹配题目。我们先看看这道题的题目描述。
题目描述
实现 strStr()函数。
给定一个 haystack字符串和一个 needle字符串，在 haystack字符串中找出 needle 字符串出现的第一个位置 (从0开始)。如果不存在，则返回 -1。
示例 1:
输入: haystack = "hello", needle = "ll"输出: 2示例 2:
输入: haystack = "aaaaa", needle = "bba"输出: -1说明:
当 needle是空字符串时，我们应当返回什么值呢？这是一个在面试中很好的问题。
对于本题而言，当 needle是空字符串时我们应当返回 0 。这与C语言的 strstr()以及 Java的 indexOf()定义相符。
分析
我们可以称 haystack字符串为母字符串， needle字符串为子字符串，这个题目是让我们在母字符串中寻找子字符串，如果存在，返回子字符串在母字符串中是第一个字符出现的位置，如果不存在，则返回 -1。在题目的说明部分指出，子字符串为空字符串时，返回 0。对于这样的题目，我们首先想到是暴力求解，一个一个字符去查找。对示例1的具体分析过程如下图所示：
上述分析所对应的 java代码如下所示：
class Solution { public int strStr(String haystack, String needle) {
int lenHaystack = haystack.length(); // 母字符串长度 int lenNeedle = needle.length(); // 子字符串长度 int leftHaystack = 0; // 母字符串的左指针，用来标识子字符串在母字符串中的第一个字符 int rightHaystack = 0; // 母字符串的右指针，用来标识子字符串在母字符串中的当前字符 int curNeedle = 0; // 子字符串的当前字符指针
// 当子字符串为空字符串时，返回0 if(lenNeedle == 0){ return 0; }
while(leftHaystack <= lenHaystack - lenNeedle) { // 如果母字符串中rightHaystack指向的字符与子字符串curNeedle指向的字符相等，移动母字符串中的rightHaystack指针和子字符串中的rightHaystack指针 while (haystack.charAt(rightHaystack) == needle.charAt(curNeedle)) { if (curNeedle == lenNeedle - 1) { // 如果子字符串遍历结束，则直接返回leftHaystack即可 return leftHaystack; } rightHaystack++; curNeedle++; }
// 如果母字符串中rightHaystack指向的字符与子字符串curNeedle指向的字符不相等 // 移动母字符串中的leftHaystack指针和rightHaystack指针 // 并将子字符串中的curNeedle指针初始化 leftHaystack++; rightHaystack = leftHaystack; curNeedle = 0; }
return -1; }}
Github地址
LeetCode-28 实现strStr()：https://github.com/JacobLei/leetcode/blob/master/src/main/java/A28_ImplementstrStr.java
参考链接
实现strStr()：https://leetcode-cn.com/problems/implement-strstr/
本文参与 腾讯云自媒体同步曝光计划，分享自微信公众号。
原始发表：2019-06-10，如有侵权请联系 cloudcommunity@tencent.com 删除
评论
登录后参与评论
推荐阅读
目录
腾讯云开发者
