【Day 83 】2024-02-06 - 28 实现 strStr(

[azl397985856]

28 实现 strStr(

入选理由

暂无

题目地址

[ 之 BF&RK 篇）

https://leetcode-cn.com/problems/implement-strstr/]( 之 BF&RK 篇）

https://leetcode-cn.com/problems/implement-strstr/)

前置知识

• 滑动窗口
• 字符串
• Hash 运算

题目描述

实现 strStr() 函数。

给定一个 haystack 字符串和一个 needle 字符串，在 haystack 字符串中找出 needle 字符串出现的第一个位置 (从0开始)。如果不存在，则返回  -1。

示例 1:

输入: haystack = "hello", needle = "ll"
输出: 2
示例 2:

输入: haystack = "aaaaa", needle = "bba"
输出: -1
说明:

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

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

[Chloe-C11]

class Solution:
    def strStr(self, haystack: str, needle: str) -> int:
        if haystack == needle: return 0
        n = len(needle)
        j = 0
        while j <= len(haystack)-n:
            if haystack[j:j+n] == needle:
                return j  
            j += 1
        return -1

[snmyj]

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

[Danielyan86]

class Solution:
    def strStr(self, haystack: str, needle: str) -> int:
        if needle not in haystack: return -1
        for i in range(len(haystack)):
            if haystack[i:len(needle)+i] == needle:
                return i

[adfvcdxv]

var strStr = function (haystack, needle) {
const n = haystack.length, m = needle.length;
if (m === 0) {
return 0;
}
const pi = new Array(m).fill(0);
for (let i = 1, j = 0; i < m; i++) {
while (j > 0 && needle[i] !== needle[j]) {
j = pi[j - 1];
}
if (needle[i] == needle[j]) {
j++;
}
pi[i] = j;
}
for (let i = 0, j = 0; i < n; i++) {
while (j > 0 && haystack[i] != needle[j]) {
j = pi[j - 1];
}
if (haystack[i] == needle[j]) {
j++;
}
if (j === m) {
return i - m + 1;
}
}
return -1;
};

[larscheng]

思路

暴力遍历（滑动窗口）

代码

class Solution {
    public int strStr(String haystack, String needle) {
        int length_a = haystack.length();
        int length_b = needle.length();
        if (length_a<length_b){
            return -1;
        }

        for (int i = 0; i <= length_a-length_b; i++) {
            String substring = haystack.substring(i, i + length_b);
            if (substring.equals(needle)){
                return i;
            }
        }
        return -1;
    }
}

复杂度

• 时间复杂度：O(m*n) m为haystack字符串长度，n为needle字符串长度
• 空间复杂度：O(1)

[Junru281]

class Solution {
    public int strStr(String haystack, String needle) {
        if (needle == null || needle.isEmpty()) {
            return 0;
        }
        
        int i = 0;
        while (i < haystack.length()) {
            int j = 0;
            int match = 0; 
            while (i + j < haystack.length() && j < needle.length() && haystack.charAt(i + j) == needle.charAt(j)) {
                match++; 
                j++;
            }
            if (match == needle.length()) {
                return i;
            }
            i++;
        }
        
        return -1;
    }
}