首页
学习
活动
专区
工具
TVP
发布
社区首页 >专栏 >LeetCode-28. Implement strStr() | 实现 strStr()

LeetCode-28. Implement strStr() | 实现 strStr()

作者头像
Zoctopus
发布2021-02-25 17:15:42
3570
发布2021-02-25 17:15:42
举报

题目

LeetCode LeetCode-cn

Implement strStr().

Return the index of the first occurrence of needle in haystack, or -1 if needle is not part of haystack.

Clarification:

What should we return when needle is an empty string? This is a great question to ask during an interview.

For the purpose of this problem, we will return 0 when needle is an empty string. This is consistent to C's strstr() and Java's indexOf().

Example 1:
Input: haystack = "hello", needle = "ll"
Output: 2

Example 2:
Input: haystack = "aaaaa", needle = "bba"
Output: -1

Example 3:
Input: haystack = "", needle = ""
Output: 0
 
Constraints:
0 <= haystack.length, needle.length <= 5 * 104
haystack and needle consist of only lower-case English characters.

题解

难度简单。 这道题就是说要找到needlehaystack第一个出现的位置,如果没有出现就返回-1

解法一:暴力法

//Go
func strStr(haystack string, needle string) int {
    //考虑特殊情况
    if len(haystack) == 0 && len(needle) == 0 {
        return 0
    }
    if len(haystack) == 0 {
        return -1
    }
    if len(needle) == 0 {
        return 0
    }
    if len(haystack) < len(needle) {
        return -1
    }
    len_h := len(haystack)  //获取haystack字符串的长度
    len_n := len(needle)  //获取needle字符串的长度
    for i:=0;i<len_h-len_n+1;i++ {
        j := 0;  //子串每次都要重头开始遍历
        for ;j<len_n;j++ {
            if (haystack[i+j] != needle[j]) {
                break;
            }
        }
        if (j == len_n) {
            return i;
        }
            
    }

    return -1; 
}

执行结果:

leetcode-cn:
执行用时:0 ms, 在所有 Go 提交中击败了100.00%的用户
内存消耗:2.2 MB, 在所有 Go 提交中击败了64.54%的用户

leetcode:
Runtime: 0 ms, faster than 100.00% of Go online submissions for Implement strStr().
Memory Usage: 2.3 MB, less than 100.00% of Go online submissions for Implement strStr().

参考资料

Golang中的内置函数strings.Index也可以实现,可以参考它的源码实现。

//Go
import "strings"
func strStr(haystack string, needle string) int {
    return strings.Index(haystack,needle)
}
本文参与 腾讯云自媒体分享计划,分享自作者个人站点/博客。
原始发表:2021-02-12 ,如有侵权请联系 cloudcommunity@tencent.com 删除

本文分享自 作者个人站点/博客 前往查看

如有侵权,请联系 cloudcommunity@tencent.com 删除。

本文参与 腾讯云自媒体分享计划  ,欢迎热爱写作的你一起参与!

评论
登录后参与评论
0 条评论
热度
最新
推荐阅读
目录
  • 题目
  • 题解
    • 解法一:暴力法
    • 参考资料
    领券
    问题归档专栏文章快讯文章归档关键词归档开发者手册归档开发者手册 Section 归档