1. 首页
  2. Leetcode经典148题

leetCode-28-Implement-strStr

题目描述(简单难度)

leetCode-28-Implement-strStr

返回一个字符串 needle 在另一个字符串 haystack 中开始的位置,如果不存在就返回 -1 ,如果 needle 长度是 0 ,就返回 0 。

就是一一比较就好,看下代码吧。

public int strStr(String haystack, String needle) {
    if (needle.length() == 0) {
        return 0;
    }
    int j = 0;
    //遍历每个字符
    for (int i = 0; i < haystack.length(); i++) {
        //相等的话计数加 1 
        if (haystack.charAt(i) == needle.charAt(j)) {
            j++;
            //长度够了就返回
            if (j == needle.length()) {
                return i - j + 1;
            }
            // 不相等的话 j 清零,
            // 并且 i 回到最初的位置,之后就进入 for 循环中的 i++,从下个位置继续判断
        } else {
            i = i - j;
            j = 0;
        }
    }
    return -1;
}

时间复杂度:假设 haystack 和 needle 的长度分别是 n 和 k,对于每一个 i ,我们最多执行 k – 1 次,总共会有 n 个 i ,所以时间复杂度是 O(kn)。

空间复杂度:O(1)。

我们再看下别人的代码,用两个 for 循环。但本质其实是一样的,但可能会更好理解些吧。

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

总的来说,还是比较简单的,就是简单的遍历就实现了。

作者:windliang

来源:https://windliang.cc

JS中文网,Javascriptc中文网是中国领先的新一代开发者社区和专业的技术媒体,一个帮助开发者成长的社区,是给开发者用的 Hacker News,技术文章由为你筛选出最优质的干货,其中包括:Android、iOS、前端、后端等方面的内容。目前已经覆盖和服务了超过 300 万开发者,你每天都可以在这里找到技术世界的头条内容。

本文著作权归作者所有,如若转载,请注明出处

转载请注明:文章转载自「 Java极客技术学习 」https://www.javajike.com

标题:leetCode-28-Implement-strStr

链接:https://www.javajike.com/article/3165.html

« leetCode-27-Remove-Element
leetCode-29-Divide-Two-Integers»

相关推荐

QR code