LeetCode 28. Implement strStr()题目分析代码

Implement strStr(). Returns the index of the first occurrence of needle in haystack, or -1 if needle is not part of haystack. Subscribe to see which companies asked this question.

题目

对于一个给定的 source 字符串和一个 target 字符串,你应该在 source 字符串中找出 target 字符串出现的第一个位置(从0开始)。如果不存在,则返回 -1。

说明 在面试中我是否需要实现KMP算法? 不需要,当这种问题出现在面试中时,面试官很可能只是想要测试一下你的基础应用能力。当然你需要先跟面试官确认清楚要怎么实现这个题。

样例 如果 source = "source"和 target = "target",返回 -1。 如果 source = "abcdabcdefg"和 target = "bcd",返回 1。

分析

不用kmp算法,用简单的二重循环判断。 首先第一重循环,source的第一位到减去target长度的位数加一(这样是为了处理两个串都是空的情况) 第二重循环,每次都和target的每一位进行比较是否相等,如果找到一位不相等的就直接跳出循环。 最后如果能全部循环完成,就说明这个串是相等的。这样就可以返回所在下标了,也就是i。 这种通过判断不等来判断相等的思想是算法中常用的,需要好好体会掌握

代码

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

Paste_Image.png

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

发表于

我来说两句

0 条评论
登录 后参与评论

相关文章

来自专栏斑斓

编程修炼 | Scala中Stream的应用场景及其实现原理

假设一个场景需要在50个随机数中找到前两个可以被3整除的数字。听起来很简单,我们可以这样来写: def randomList = (1 to 50).map(_...

30050
来自专栏battcn

一起学设计模式 - 迭代器模式

迭代器模式听起来可能感觉很陌生,但是实际上, 迭代器模式是所有设计模式中最简单也是最常用的设计模式,正是因为太常用了,所以导致很多人忽略了它的存在。

9140
来自专栏ThoughtWorks

【好声音】 Scala中Stream的应用场景及其实现原理

说明:本文包含了大量Scala源代码。如果你在手机上阅读体验不佳,请移步到“阅读原文”,在电脑上或者微信电脑版上访问作者博客,阅读全文。 假设一个场景需要在50...

36050
来自专栏一英里广度一英寸深度的学习

二叉树的插入和搜索--python实现

在二分查找基于数组,在插入删除时需要移动较多节点,采用二叉树的数据结构,更好的实现插入、删除操作。

44910
来自专栏苦逼的码农

【面试现场】如何在500w个单词中统计特定前缀的单词有多少个?

题目:我有500w个单词,你帮忙设计一个数据结构来进行存储,存好之后,我有两个需求。

11810
来自专栏java系列博客

java Arrays.aslist用法

19160
来自专栏静晴轩

JavaScript 字符串实用常操纪要

JavaScript 字符串用于存储和处理文本。因此在编写 JS 代码之时她总如影随形,在你处理用户的输入数据的时候,在读取或设置 DOM 对象的属性时,在操作...

40770
来自专栏机器学习实践二三事

单链表判断是否有环和环起始节点

面试的滴滴研究院暑期实习生,岗位机器学习,二面除了电话面还要视频面试写代码,两个问题: 单链表判断是否有环以及找出环开始的节点 建立二叉排序树并进行中序遍历 因...

20280
来自专栏机器学习入门

挑战程序竞赛系列(77):4.3 2-SAT(1)

挑战程序竞赛系列(77):4.3 2-SAT(1) 传送门:POJ 3683: Priest John’s Busiest Day 题意: 有n个婚礼,每个...

21060
来自专栏云霄雨霁

子字符串查找----Rabin-Karp算法(基于散列)

27700

扫码关注云+社区

领取腾讯云代金券