leetcode

leetcode 28题

Posted by franki on June 6, 2021

leetcode 28题 实现 strStr()

实现 strStr() 函数。

给你两个字符串 haystack 和 needle ，请你在 haystack 字符串中找出 needle 字符串出现的第一个位置（下标从 0 开始）。如果不存在，则返回  -1 。

说明：

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

对于本题而言，当 needle 是空字符串时我们应当返回 0 。这与 C 语言的 strstr() 以及 Java 的 indexOf() 定义相符。

示例1

输入：haystack = "hello", needle = "ll"
输出：2

示例2

输入：haystack = "aaaaa", needle = "bba"
输出：-1

思路

设置两个指针，每一次循环，对比两个指针的关系，直到满足条件，或者超出条件即可退出

代码

/**
 * @param {string} haystack
 * @param {string} needle
 * @return {number}
 */
var strStr = function(haystack, needle) {
    for (let i=0; ; i++) {
        for (let j=0; ; j++) {
            if (j === needle.length) {
                return i;
            }
            if (i+j === haystack.length) {
                return -1;
            }
            if (needle[j] !== haystack[i+j]) {
                break;
            }
        }
    }
};

复杂度分析:

  • 时间复杂度: O(N^2)
  • 空间复杂度：O(1)
CATALOG
    FEATURED TAGS
    前端开发 H5 JavaScript 设计模式 browser jQuery 源码分析 生活 leetcode Array Stack Queue Linked List 剑指offer Binary Search Tree Binary Tree Breadth-First Search Depth-First Search String Set Binary Search Sliding Window Backtracking Dynamic Programming Two Pointers Union Find Sort Bit Operation Recursion Map Graph Search Hash LinkedList QuickSort Trie Design MinHeap Traverse Min Heap Node.js BackEnd SQL MySQL Design Patterns Network 计算机网络 Python
    FRIENDS