让我们一起啃算法---- 实现 strStr

三斤和他的喵的个人博客 / 192 / 2 / 创建于 4年前 / 更新于 4年前

实现 strStr（Implement-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() 定义相符。
来源：力扣

本题有很多种解题方式，为了再巩固一下 双指针解题思路 这题我们还是选用这种思路来解。
建议再结合让我们一起啃算法—-移除元素和让我们一起啃算法—-删除排序数组中的重复项两篇文章仔细体会一下 双指针思路。

解题思路

初始化 i 指向 needle 字符串的第一个字符， j 指向 haystack 字符串的第一个字符。比较 needle[i] 与 haystack[j] 的字符是否相等：相等则i++、j++；不想等则 i 重新指向 needle 字符串的第一个字符，j 指向上一次初始位置的后一个字符。

注： j 指向上一次初始位置的后一个字符的计算方式为： j = j - i + 1。可以自己造个数组，推算一下这个规律哟。

流程图如下：

代码实现

GO语言实现

func strStr(haystack string, needle string) int {

    // 子串为空则返回 0
    if needle == "" {
        return 0
    }

    i := 0
    j := 0
    for j < len(haystack) {
        // 判断 haystack[j] 与 needle[i] 是否相等，不想等，则 i 重新指向 needle 字符串的首字符，即 i = 0
        // j 指向 j上一次初始化的后一个字符串，即 j = j - i + 1
        if haystack[j] != needle[i] {
            j = j - i + 1
            i = 0
        } else {
            // haystack[j] 与 needle[i] 相等，则先判断 i 是否已经最大
            // 是的话就返回 needle 在 haystack 的第一个位置，计算方式： j - i
            if i == len(needle) -1 {
                return j - i
            }
            // 如果 i 不是 needle 的最大索引，那么 j 向后移动一位，i 向后移动一位，继续比较
            j++
            i++
        }
    }
    // j 越界了，说明不存在子串 needle，即返回 -1
    return -1
}

总结

每天进步一点点，加油！
算法教程项目，每天更新一题，点个 star 支持一下呀：
https://github.com/wx-satellite/learning-a…

算法数据结构 leetcode 双指针思路

本作品采用《CC 协议》，转载必须注明作者和本文链接

三斤

三斤和他的喵

课程读者 172 声望

一个PHPer的修行之路。欢迎大家关注我的公众号《三斤和他的喵》

4 人点赞

从小程序个人账户申请开始，带你一步步进行开发一个微信小程序，直到提交微信控制台上线发布。

从零开始带你一步步开发一个 Go 博客项目，让你在最短的时间内学会使用 Go 进行编码。项目结构很大程度上参考了 Laravel。

推荐文章：

更多推荐...

面试 POPER 的后端开发工程师的离奇经历 35 / 104 |

分享创造

📙《高并发的哲学原理》开源图书发布十一天 star 数已经破千！ 47 / 16 |

博客

PHP面试高薪宝典系列: 常见基础算法（附完整代码） 23 / 3 |

博客

强一致性的分布式事务几种模式对比（php有了新方案） 33 / 20 |

博客

贴合生产的 MySQL 优化思路 60 / 5 |

博客

PHP实现汉诺塔算法 21 / 9 |

讨论数量: 2

captain2021

Laravel 5.8 译者 422 声望 / 开发 @ 谈笑风生

function strstr2($str, $search) {
    $count = strlen($str);
    $tmpLength = 0;
    $tmp = [];
    $i = 0;
    while ($i < $count) {
        // 未找到置为初始值
        if ($str[$i] !== $search[$tmpLength]) {
            $tmp = [];
            $tmpLength = 0;
            if ($i === $count - 1) {
                return -1;
            }
        } else {
            // 找到匹配元素，继续执行
            $tmp[$tmpLength] = $str[$i];
            if (!isset($search[$tmpLength + 1])) {
                return $i - $tmpLength;  // 位置
                return $tmp;             // 结果集
            }
            $tmpLength++;
        }
        $i++;
    }
}
echo substr2('hello', 'll'); // output: 2

昨天仿照一个 js 版的实现了一下，效果类似

4年前评论

Littlesqx

class Solution
{
    public function strStr(string $haystack, string $needle): int
    {
        if (0 === ($lengthOfNeedle = strlen($needle))) {
            return 0;
        }

        $lengthOfHaystack = strlen($haystack);
        $diffLength = $lengthOfHaystack - $lengthOfNeedle;

        for ($i = 0, $j = 0, $k = 0; $i <= $diffLength; $i++, $j = 0, $k = $i) {
            while ($k < $lengthOfHaystack && $j < $lengthOfNeedle && $haystack[$k] === $needle[$j]) {
                $k++;
                $j++;
            }

            if ($j === $lengthOfNeedle) {
                return $k - $j;
            }
        }

        return -1;
    }
}

三斤和他的喵（楼主）

优秀 :+1:

captain2021 （作者）

@Littlesqx 大佬这些算法都是自学的还是在哪学的？

Littlesqx

@hxd 我不是大佬啊，这些不是 leetcode 的吗？有些刷过，有些跟着你们写，然后优化下，有参考其他题解

captain2021 （作者）

@Littlesqx 好的，谢谢

yzh52521

33 声望

function strStr($haystack, $needle) {
       $needle_len = strlen($needle);
        $haystack_len = strlen($haystack);
        if($needle_len == 0){
            return 0;
        }
        for ($i = 0; $i < $haystack_len; $i++) {
            $target = substr($haystack,$i,$needle_len);
            if($needle == $target){
                return $i;
            }
        }
        return -1;
}

4年前评论

讨论应以学习和精进为目的。请勿发布不友善或者负能量的内容，与人为善，比聪明更重要！

帮助

让我们一起啃算法---- 实现 strStr

实现 strStr（Implement-StrStr）

解题思路

代码实现

GO语言实现

总结

推荐文章：

社区赞助商

关于 LearnKu

资源推荐

服务提供商

其他信息

让我们一起啃算法---- 实现 strStr

实现 strStr（Implement-StrStr）

解题思路

代码实现

GO语言实现

总结

推荐文章：

社区赞助商

关于 LearnKu

资源推荐

服务提供商

其他信息

请登录