C++实现LeetCode(28.实现strStr()函数)

[LeetCode] 28. Implement strStr() 实现strStr()函数

Implement strStr().

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

Example 1:

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

Example 2:

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

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().

这道题让我们在一个字符串中找另一个字符串第一次出现的位置，那首先要做一些判断，如果子字符串为空，则返回0，如果子字符串长度大于母字符串长度，则返回 -1。然后开始遍历母字符串，这里并不需要遍历整个母字符串，而是遍历到剩下的长度和子字符串相等的位置即可，这样可以提高运算效率。然后对于每一个字符，都遍历一遍子字符串，一个一个字符的对应比较，如果对应位置有不等的，则跳出循环，如果一直都没有跳出循环，则说明子字符串出现了，则返回起始位置即可，代码如下：

class Solution {
public:
    int strStr(string haystack, string needle) {
        if (needle.empty()) return 0;
        int m = haystack.size(), n = needle.size();
        if (m < n) return -1;
        for (int i = 0; i <= m - n; ++i) {
            int j = 0;
            for (j = 0; j < n; ++j) {
                if (haystack[i + j] != needle[j]) break;
            }
            if (j == n) return i;
        }
        return -1;
    }
};

我们也可以写的更加简洁一些，开头直接套两个 for 循环，不写终止条件，然后判断假如j到达 needle 的末尾了，此时返回i；若此时 i+j 到达 haystack 的长度了，返回 -1；否则若当前对应的字符不匹配，直接跳出当前循环，参见代码如下：

解法二：

class Solution {
public:
    int strStr(string haystack, string needle) {
        for (int i = 0; ; ++i) {
            for (int j = 0; ; ++j) {
                if (j == needle.size()) return i;
                if (i + j == haystack.size()) return -1;
                if (needle[j] != haystack[i + j]) break;
            }
        }
        return -1;
    }
};

到此这篇关于C++实现LeetCode(28.实现strStr()函数)的文章就介绍到这了,更多相关C++实现实现strStr()函数内容请搜索我们以前的文章或继续浏览下面的相关文章希望大家以后多多支持我们！

赞 (0)

相关推荐

  • C++实现LeetCode(21.混合插入有序链表)

    [LeetCode] 21. Merge Two Sorted Lists 混合插入有序链表 Merge two sorted linked lists and return it as a new list. The new list should be made by splicing together the nodes of the first two lists. Example: Input: 1->2->4, 1->3->4 Output: 1->1->2

  • C++实现LeetCode(24.成对交换节点)

    [LeetCode] 24. Swap Nodes in Pairs 成对交换节点 Given a linked list, swap every two adjacent nodes and return its head. You may not modify the values in the list's nodes, only nodes itself may be changed. Example: Given 1->2->3->4 , you should return t

  • C++实现LeetCode(88.混合插入有序数组)

    [LeetCode] 88. Merge Sorted Array 混合插入有序数组 Given two sorted integer arrays nums1 and nums2, merge nums2 into nums1 as one sorted array. Note: The number of elements initialized in nums1and nums2 are m and n respectively. You may assume that nums1 has

  • C++实现LeetCode(22.生成括号)

    [LeetCode] 22. Generate Parentheses 生成括号 Given n pairs of parentheses, write a function to generate all combinations of well-formed parentheses. For example, given n = 3, a solution set is: [ "((()))", "(()())", "(())()", &qu

  • C++实现LeetCode(83.移除有序链表中的重复项)

    [LeetCode] 83. Remove Duplicates from Sorted List 移除有序链表中的重复项 Given a sorted linked list, delete all duplicates such that each element appear only once. Example 1: Input: 1->1->2 Output: 1->2 Example 2: Input: 1->1->2->3->3 Output: 1-

  • C++实现LeetCode(23.合并k个有序链表)

    [LeetCode] 23. Merge k Sorted Lists 合并k个有序链表 Merge k sorted linked lists and return it as one sorted list. Analyze and describe its complexity. Example: Input: [ 1->4->5, 1->3->4, 2->6 ] Output: 1->1->2->3->4->4->5->6 这

  • C++实现LeetCode(25.每k个一组翻转链表)

    [LeetCode] 25. Reverse Nodes in k-Group 每k个一组翻转链表 Given a linked list, reverse the nodes of a linked list k at a time and return its modified list. k is a positive integer and is less than or equal to the length of the linked list. If the number of n

  • C++实现LeetCode(27.移除元素)

    [LeetCode] 27. Remove Element 移除元素 Given an array nums and a value val, remove all instances of that value in-place and return the new length. Do not allocate extra space for another array, you must do this by modifying the input array in-place with

  • C++实现LeetCode(26.有序数组中去除重复项)

    [LeetCode] 26. Remove Duplicates from Sorted Array 有序数组中去除重复项 Given a sorted array nums, remove the duplicates in-place such that each element appear only once and return the new length. Do not allocate extra space for another array, you must do this

  • C++实现LeetCode(28.实现strStr()函数)

    [LeetCode] 28. Implement strStr() 实现strStr()函数 Implement strStr(). Return the index of the first occurrence of needle in haystack, or -1 if needle is not part of haystack. Example 1: Input: haystack = "hello", needle = "ll" Output: 2 E

  • PHP使用strstr()函数获取指定字符串后所有字符的方法

    本文实例讲述了PHP使用strstr()函数获取指定字符串后所有字符的方法.分享给大家供大家参考,具体如下: PHP的strstr()函数可搜索字符串在另一字符串中的第一次出现位置,并返回字符串的剩余部分. strstr()函数定义如下: strstr(string,search,before_search) 参数说明: string 必需.规定被搜索的字符串. search  必需.规定所搜索的字符串. 如果此参数是数字,则搜索匹配此数字对应的 ASCII 值的字符. before_searc

  • PHP用strstr()函数阻止垃圾评论(通过判断a标记)

    strstr() 函数搜索一个字符串在另一个字符串中的第一次出现.该函数返回字符串的其余部分(从匹配点).如果未找到所搜索的字符串,则返回 false. 语法:strstr(string,search) 参数string,必需.规定被搜索的字符串. 参数search,必需.规定所搜索的字符串.如果该参数是数字,则搜索匹配数字 ASCII 值的字符. 该函数对大小写敏感.如需进行大小写不敏感的搜索,请使用 stristr(). strstr()函数简单演示 复制代码 代码如下: <?phpecho

  • C++中strstr函数的实现方法总结

    C++中strstr函数的实现方法总结 函数说明: 包含文件:string.h 函数名: strstr 函数原型:extern char *strstr(char *str1, char *str2); 功能:从字符串str1中查找是否有字符串str2, 如果有,从str1中的str2位置起,返回str1的指针,如果没有,返回null. 返回值:返回该位置的指针,如找不到,返回空指针. 方法一: #include <iostream> #include <assert.h> usi

  • C 语言中strstr函数实例详解

    C 语言中strstr函数实例详解

    C 语言中strstr函数实例详解 strstr函数 strstr(str1,str2) 函数用于判断字符串str2是否是str1的子串.如果是,则该函数返回str2在str1中首次出现的地址:否则,返回NULL const char* strstr(const char* str1,const char* str2); char* strstr(char* str1,const char* str2); 库中实现的strstr #include <stdio.h> #include <

  • PHP strstr 函数判断字符串是否否存在的实例代码

    PHP strstr 定义和用法 strstr() 函数搜索一个字符串在另一个字符串中的第一次出现. 该函数返回字符串的其余部分(从匹配点).如果未找到所搜索的字符串,则返回 false. 语法 strstr(string,search) 参数 描述 string 必需.规定被搜索的字符串. search 必需.规定所搜索的字符串.如果该参数是数字,则搜索匹配数字 ASCII 值的字符. 提示和注释 注释:该函数是二进制安全的. 注释:该函数对大小写敏感.如需进行大小写不敏感的搜索,请使用 st

  • C语言模拟实现strstr函数的示例代码

    C语言模拟实现strstr函数的示例代码

    目录 strstr函数介绍 BF算法介绍 BF算法模拟实现strstr函数 KMP算法介绍 KMP算法模拟实现strstr函数 strstr函数介绍 C语言提供了字符串匹配函数 strstr 函数,请看文档简介. 这个函数是用来匹配 str2 是否包含在 str1 字符串中,如果匹配成功,则返回指向str1中第一个出现的str2的指针,如果str2不是str1的一部分,则返回空指针.我们不妨举例说明,请看下面代码,调用 strstr 函数需要引入string.h头文件,我们发现,s1字符串中可以

  • java算法入门之有效的括号删除有序数组中的重复项实现strStr

    java算法入门之有效的括号删除有序数组中的重复项实现strStr

    目录 1.LeetCode 20.有效的括号 题目 小编菜解 思路及算法 大神解法 2.LeetCode 26.删除有序数组中的重复项 题目 小编菜解初版 小编菜解改进版 思路及算法 大神解法 3.LeetCode 28.实现strStr 题目 小编菜解 大神解法 也许,我们永远都不会知道自己能走到何方,遇见何人,最后会变成什么样的人,但一定要记住,能让自己登高的,永远不是别人的肩膀,而是挑灯夜战的自己,人生的道路刚刚启程,当你累了倦了也不要迷茫,回头看一看,你早已不再是那个年少轻狂的少年. 1

  • c++ KMP字符串匹配算法

    目录 KMP算法简介 前缀表 如何构造前缀表next数组 如何用next数组进行模板匹配 总结 KMP算法简介 KMP算法(Knuth-Morris-Pratt 算法)是一个著名的字符串匹配算法,它主要的思想是当出现字符串不匹配时,可以知道一部分之前已经匹配的文本内容,可以利用这些信息避免从头再去做匹配. 本章以力扣 28. 实现 strStr()为例子进行讲解. 力扣28.实现strStr()函数:给你两个字符串 haystack 和 needle ,请你在 haystack 字符串中找出 n

  • php strstr查找字符串中是否包含某些字符的查找函数

    PHP 判断字符串是否包含其它字符 以下几个函数均可用来判断某字符串是否包含另外一个字符串PHP 中判断一个字符串是否包含其它字符是很常见的操作. 虽然很简单,但还是写了几个函数,质量可能不是很高,权当锻炼. 如果这几个函数恰好能帮上你的忙,我将会很高兴的.这几个函数中,我比较喜欢第四个... 复制代码 代码如下: <?php /** * 以下几个函数均可用来判断某字符串是否包含另外一个字符串 * PHP 中判断一个字符串是否包含其它字符是很常见的操作. * 虽然很简单,但还是写了几个函数,质量

随机推荐