专栏首页江涛的博客leetcode - 实现strStr()

leetcode - 实现strStr()

题意

实现strStr()函数。

给你两个字符串haystackneedle ,请你在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

提示

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

出处

链接:https://leetcode-cn.com/problems/implement-strstr/

思路

这里对题目给出的题意我们先考虑特殊情况,比如最后提到的空字符串返回什么问题, 然后可以根据两个参数的长度进行分类讨论,之后的话做法是把haystack所有可以出现的位置存到一个数组里面,然后我们去遍历它,在里面遍历needle,如果每个都相等的话,那么我们就把存进数组的左指针返回

代码

const strStr = function (haystack, needle) {
  if (needle === '') {
    return 0;
  }
  const haystack_len = haystack.length;
  const needle_len = needle.length;
  if (needle_len > haystack_len) {
    return -1;
  } else if (needle_len === haystack_len) {
    return haystack === needle ? 0 : -1;
  }
  const target = needle[0];
  const position = [];
  for (const index in haystack) {
    if (haystack[index] === target) {
      position.push(+index);
    }
  }
  for (const left of position) {
    let right = left;
    for (let i = 0; i < needle_len; i++) {
      if (haystack[right] === needle[i]) {
        if (i === needle_len - 1) {
          return left;
        }
        right++;
      } else {
        break;
      }
    }
  }
  return -1;
};

export default strStr;

测试

import strStr from '../../code/leetcode/28';

describe('test function strStr:', () => {
  test('test case str="mississippi", needle="mississippii", target = -1', () => {
    const data = strStr('mississippi', 'mississippii');
    expect(data).toEqual(-1);
  });

  test('test case str="mississippi", needle="mississippii", target = -1', () => {
    const data = strStr('mississippi', 'issi');
    expect(data).toEqual(1);
  });

  test('test case str="a", needle="a", target = 0', () => {
    const data = strStr('a', 'a');
    expect(data).toEqual(0);
  });

  test('test case str="abc", needle="c", target = 2', () => {
    const data = strStr('abc', 'c');
    expect(data).toEqual(2);
  });

  test('test case str="hello", needle="ll", target = 2', () => {
    const data = strStr('hello', 'll');
    expect(data).toEqual(2);
  });

  test('test case str="aaaaa", needle="bba", target = -1', () => {
    const data = strStr('aaaaa', 'bba');
    expect(data).toEqual(-1);
  });

  test('test case str="", needle="", target = 0', () => {
    const data = strStr('', '');
    expect(data).toEqual(0);
  });
});

说明

本文首发于 GitHub 仓库https://github.com/ataola/coding,线上阅读地址:https://zhengjiangtao.cn/coding/,转载请注明出处,谢谢!

本文分享自微信公众号 - 前端路桥(ataola),作者:璀错

原文出处及转载信息见文内详细说明,如有侵权,请联系 yunjia_community@tencent.com 删除。

原始发表时间:2021-04-20

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

我来说两句

0 条评论
登录 后参与评论

相关文章

  • LeetCode | 实现strStr()

      该题就是两层循环,第一层循环主要是遍历字符串,第二层循环用来进行匹配。实现代码如下:

    码农UP2U
  • 【LeetCode】 实现 strStr()

    版权声明:本文为博主原创文章,遵循 CC 4.0 BY 版权协议,转载请附上原文出处链接和本声明。 ...

    韩旭051
  • LeetCode - 实现strStr()

    LeetCode第28题,难度简单。这题.怎么说呢,反正我的写法很简单,当然相对的就是运算速度有点慢。

    晓痴
  • LeetCode 28. 实现 strStr()

    给定一个 haystack 字符串和一个 needle 字符串,在 haystack 字符串中找出 needle 字符串出现的第一个位置 (从0开始)。如果不存...

    freesan44
  • LeetCode-28.实现 strStr()

    给定一个 haystack 字符串和一个 needle 字符串,在 haystack 字符串中找出 needle 字符串出现的第一个位置 (从0开始)。如果不存...

    悠扬前奏
  • LeetCode | 28.实现strStr()

    这次来写一下 LeetCode 的第 28 题,实现 strStr()。

    码农UP2U
  • LeetCode-28 实现strStr()

    今天我们学习第28题实现strStr(),这个题目是一个典型的字符串匹配题目。我们先看看这道题的题目描述。

    用户3470542
  • ​ LeetCode 28:实现strStr() Implement strStr()

    给定一个 haystack 字符串和一个 needle 字符串,在 haystack 字符串中找出 needle 字符串出现的第一个位置 (从0开始)。如果不存...

    爱写bug
  • LeetCode 28:实现strStr() Implement strStr()

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

    爱写bug
  • 【刷穿 LeetCode】28. 实现 strStr()(简单)

    给定一个 haystack 字符串和一个 needle 字符串,在 haystack 字符串中找出 needle 字符串出现的第一个位置 (从0开始)。如果不存...

    宫水三叶的刷题日记
  • 力扣 (LeetCode)-28. 实现 strStr()|刷题打卡

    Github来源:力扣 (LeetCode)|刷题打卡 | 求星星 ✨ | 给个❤️关注,❤️点赞,❤️鼓励一下作者

    达达前端
  • LeetCode-28. Implement strStr() | 实现 strStr()

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

    Zoctopus
  • Swift 实现strStr() - LeetCode

    当 needle 是空字符串时,我们应当返回什么值呢?这是一个在面试中很好的问题。

    韦弦zhy
  • LeetCode题目28:实现strStr()

    给定一个 haystack 字符串和一个 needle 字符串,在 haystack 字符串中找出 needle 字符串出现的第一个位置 (从0开始)。如果不存...

    二环宇少
  • 【小Y学算法】⚡️每日LeetCode打卡⚡️——15.实现 strStr()

    给你两个字符串 haystack和 needle,请你在 haystack 字符串中找出 needle字符串出现的第一个位置(下标从 0 开始)。

    呆呆敲代码的小Y
  • ​LeetCode刷题实战28:实现 strStr()

    算法的重要性,我就不多说了吧,想去大厂,就必须要经过基础知识和业务逻辑面试+算法面试。所以,为了提高大家的算法能力,这个公众号后续每天带大家做一道算法题,题目就...

    程序IT圈
  • 【必背模板】字符串匹配问题的通用解法:KMP 算法 ...

    这是 LeetCode 上的「28. 实现 strStr()」,难度为 Easy。

    宫水三叶的刷题日记
  • ​LeetCode刷题实战28:实现 strStr()

    算法的重要性,我就不多说了吧,想去大厂,就必须要经过基础知识和业务逻辑面试+算法面试。所以,为了提高大家的算法能力,这个公众号后续每天带大家做一道算法题,题目就...

    程序IT圈
  • 实现 strStr()

    给定一个 haystack 字符串和一个 needle 字符串,在 haystack 字符串中找出 needle 字符串出现的第一个位置 (从0开始)。如果不存...

    用户4456933

扫码关注云+社区

领取腾讯云代金券