【刷题记录】28. 实现 strStr()-阿里云开发者社区

【刷题记录】28. 实现 strStr()

2022-05-29 99

版权

本文内容由阿里云实名注册用户自发贡献，版权归原作者所有，阿里云开发者社区不拥有其著作权，亦不承担相应法律责任。具体规则请查看《阿里云开发者社区用户服务协议》和《阿里云开发者社区知识产权保护指引》。如果您发现本社区中有涉嫌抄袭的内容，填写侵权投诉表单进行举报，一经查实，本社区将立刻删除涉嫌侵权内容。

简介： 【刷题记录】28. 实现 strStr()

一、题目描述

来源：力扣（LeetCode）

实现 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

示例 3：

输入：haystack = "", needle = ""

输出：0

二丶思路分析

暴力匹配

我们直接以haystack的每一个字符为起点，长度为needle 的子串与 needle 对比

匹配，返回起点所在位置
不匹配，继续下一个子串
所有都不满足返回 -1

三、代码实现

class Solution {
    public int strStr(String haystack, String needle) {
        int len1 = haystack.length();
        int len2 = needle.length();
for (int i =0; i + len2 <= len1; i++) {
            boolean flag =true;
for (int j =0; j < len2; j++) {
if (haystack.charAt(i + j) != needle.charAt(j)) {
                    flag =false;
                    break;
                }
            }
if (flag) {
                return i;
            }
        }
        return -1;
    }
}

复杂度分析

时间复杂度：

网络异常，图片无法展示
|

，其中 n 是字符串 haystack 的长度，m 是字符串 needle 的长度
空间复杂度：

网络异常，图片无法展示
|

运行结果

网络异常，图片无法展示

官方的另外解法

看官方题解，除了暴力，还可以使用 KMP 算法来解决。
详细的题解太长，就不列出来，有兴趣的可以自行点击查看。

这里只贴出来代码实现

class Solution {
    public int strStr(String haystack, String needle) {
        int n = haystack.length(), m = needle.length();
if (m ==0) {
            return 0;
        }
        int[] pi = new int[m];
for (int i =1, j =0; i < m; i++) {
while (j > 0 && needle.charAt(i) != needle.charAt(j)) {
                j = pi[j -1];
            }
if (needle.charAt(i) == needle.charAt(j)) {
                j++;
            }
            pi[i] = j;
        }
for (int i =0, j =0; i < n; i++) {
while (j > 0 && haystack.charAt(i) != needle.charAt(j)) {
                j = pi[j -1];
            }
if (haystack.charAt(i) == needle.charAt(j)) {
                j++;
            }
if (j == m) {
                return i - m +1;
            }
        }
        return -1;
    }
}