首页 > 其他分享 >leetcode 28. Implement strStr() 实现 strStr()(简单)

leetcode 28. Implement strStr() 实现 strStr()(简单)

时间:2022-08-30 13:12:54浏览次数:91  
标签:strStr int needle 28 leetcode 字符串 Implement haystack

一、题目大意

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

提示:

  • 1 <= haystack.length, needle.length <= 104
  • haystack 和 needle 仅由小写英文字符组成

来源:力扣(LeetCode)
链接:https://leetcode.cn/problems/implement-strstr
著作权归领扣网络所有。商业转载请联系官方授权,非商业转载请注明出处。

二、解题思路

思路1:此题可用KMP算法,可以o(m+n)时间利用动态规划完成。

思路2:遍历线字符串,只需要遍历m-n长度即可,这样可以提高运算效率。然后对每个字符,都遍历一遍子字符串,一个一个字符的对应比较,如果对应位置有不等的,则跳出循环,如果一直没有跳出循环,则说明子字符串出现了,返回起始位置即可。

三、解题方法

3.1 Java实现

public class Solution {
    public int strStr(String haystack, String needle) {
        int m = haystack.length();
        int n = needle.length();
        if (m < n) {
            return -1;
        }
        for (int i = 0; i <= m - n; i++) {
            int j;
            for (j = 0; j < n; j++) {
                if (haystack.charAt(i + j) != needle.charAt(j)) {
                    break;
                }
            }
            if (j == n) {
                return i;
            }
        }
        return -1;
    }
}

四、总结小记

  • 2022/8/30 工作啊,工作啊

标签:strStr,int,needle,28,leetcode,字符串,Implement,haystack
From: https://www.cnblogs.com/okokabcd/p/16638908.html

相关文章

  • JAVA进阶--static、工具类、单例、继承--2022年8月28日
    第一节 static静态关键字1、成员变量的分类和访问分别是什么样的?静态成员变量(有static修饰,属于类,加载一次,可以被共享访问)访问格式:类名.变量......
  • day28--Java泛型01
    Java泛型011.泛型的理解和好处看一个需求:请编写程序,在ArrayList中添加三个Dog对象Dog对象含有name和age,并输出name和age(要求使用getXXX())先用传统的方法来解决--->引......
  • Codeforces Round #287 (Div. 2) B. Amr and Pins(数学/思维)
    https://codeforces.com/contest/507/problem/B题目大意:Amr有一个半径为r、圆心在点(x,y)的圆。他希望圆心在新的位置(x',y')。在一个步骤中,Amr可以将一个大头针放在......
  • 上周热点回顾(8.22-8.28)
    热点随笔:· 拒绝加班:巧用前端电子表格中构建公式树 (葡萄城技术团队)· 被一个问题卡了近两天,下班后我哭了...... (久曲健)· 一个奇葩的线上问题,导致我排查了一天......
  • 2022-08-28 第六小组 高佳誉 学习笔记
    VUE重点定义MVVM设计模式指令思维导图知识点1.定义第三方开发的,基于MVVM设计模式的,渐进式的,纯前端js框架渐进式的:可以逐步在项目中使用vue的部分功能,可以轻松......
  • [Google] LeetCode 2128 Remove All Ones With Row and Column Flips
    Youaregivenanmxnbinarymatrixgrid.Inoneoperation,youcanchooseanyroworcolumnandflipeachvalueinthatroworcolumn(i.e.,changingall0's......
  • 2022.8.28 whk 记录
    PrefacePollard-Rho学了800万年模板过不了,AC300没戏了,等AC400叭(高中生活真的好累,一点学OI的时间都没了。只能趁周末水题。Content[CF766E]Mahmoudandaxor......
  • 8/28 深入理解计算机系统笔记 内存映射
    9.8内存映射定义:将一个虚拟内存区域和一个磁盘上的对象关联起来,以初始化这个虚拟内存区域的内容的过程被称为内存映射。虚拟内存区域可以映射到下面两种类型的对象中的......
  • 8/28 深入理解计算机系统笔记 动态内存分配
    9.9动态内存分配动态内存分配器维护一个进程的虚拟内存区域,称为堆。对于每个进程,内核维护一个变量brk,它指向堆的顶部。分配器将堆视做一组不同大小的块的集合来维护。......
  • 2022.8.28
    看了下斯特林数和多项式,在旁边听hyy和lzx讲课,顺便捉了几个Bug,算是复习了一下计数。写了些多项式。之后打洛谷上的比赛,第二题不会,感觉很神奇。Todo:讲dp。改洛谷比赛题......