【Day 84 】2024-02-07 - 28 实现 strStr(

[azl397985856]

28 实现 strStr(

入选理由

暂无

题目地址

[ 之 KMP 篇）

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

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() 定义相符。

[JinhMa]

class Solution {
    public int strStr(String haystack, String needle) {

        if (needle.length() == 0)
            return 0;

        int i = 0, j = 0;

        int[] next = getNext(needle);

        while (i < haystack.length() && j < needle.length()) {

            if (haystack.charAt(i) == needle.charAt(j)) {

                i++;
                j++;
            } else {

                if (j > 0)
                    j = next[j - 1];
                else
                    i++;
            }

            if (j == needle.length())
                return i - j;
        }

        return -1;
    }

    public int[] getNext(String pattern) {

        int[] next = new int[pattern.length()];

        int j = 0;
        for (int i = 1; i < pattern.length(); i++) {

            if (pattern.charAt(i) == pattern.charAt(j))
                next[i] = ++j;
            else {

                while (j > 0 && pattern.charAt(j) != pattern.charAt(i))
                    j = next[j - 1];

                if (pattern.charAt(i) == pattern.charAt(j))
                    next[i] = ++j;
            }
        }

        return next;
    }
}

[snmyj]

class Solution {
public:
    int strStr(string haystack, string needle) {
        int n = haystack.size(), m = needle.size();
        if (m == 0) {
            return 0;
        }
        vector<int> pi(m);
        for (int 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 (int 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;
    }
};

[Danielyan86]

class Solution:
    def strStr(self, haystack: str, needle: str) -> int:
        n, m = len(haystack), len(needle)
        s, p = list(haystack), list(needle)
        # Enumerate the "starting point" of the original string
        for i in range(n - m + 1):
            # Start matching from the "starting point" of the original string and the "first character" of the pattern string
            a, b = i, 0
            while b < m and s[a] == p[b]:
                a += 1
                b += 1
            # If a complete match is found, return the index of the "starting point" of the original string
            if b == m:
                return i
        return -1

[adfvcdxv]

class Solution { public int strStr(String haystack, String needle) {

    if (needle.length() == 0)
        return 0;

    int i = 0, j = 0;

    int[] next = getNext(needle);

    while (i < haystack.length() && j < needle.length()) {

        if (haystack.charAt(i) == needle.charAt(j)) {

            i++;
            j++;
        } else {

            if (j > 0)
                j = next[j - 1];
            else
                i++;
        }

        if (j == needle.length())
            return i - j;
    }

    return -1;
}

public int[] getNext(String pattern) {

    int[] next = new int[pattern.length()];

    int j = 0;
    for (int i = 1; i < pattern.length(); i++) {

        if (pattern.charAt(i) == pattern.charAt(j))
            next[i] = ++j;
        else {

            while (j > 0 && pattern.charAt(j) != pattern.charAt(i))
                j = next[j - 1];

            if (pattern.charAt(i) == pattern.charAt(j))
                next[i] = ++j;
        }
    }

    return next;
}

}

[larscheng]

思路

KMP

代码

class Solution {
    // KMP 算法
    // ss: 原串(string)  pp: 匹配串(pattern)
    public int strStr(String ss, String pp) {
        if (pp.isEmpty()) return 0;

        // 分别读取原串和匹配串的长度
        int n = ss.length(), m = pp.length();
        // 原串和匹配串前面都加空格，使其下标从 1 开始
        ss = " " + ss;
        pp = " " + pp;

        char[] s = ss.toCharArray();
        char[] p = pp.toCharArray();

        // 构建 next 数组，数组长度为匹配串的长度（next 数组是和匹配串相关的）
        int[] next = new int[m + 1];
        // 构造过程 i = 2，j = 0 开始，i 小于等于匹配串长度 【构造 i 从 2 开始】
        for (int i = 2, j = 0; i <= m; i++) {
            // 匹配不成功的话，j = next(j)
            while (j > 0 && p[i] != p[j + 1]) j = next[j];
            // 匹配成功的话，先让 j++
            if (p[i] == p[j + 1]) j++;
            // 更新 next[i]，结束本次循环，i++
            next[i] = j;
        }

        // 匹配过程，i = 1，j = 0 开始，i 小于等于原串长度 【匹配 i 从 1 开始】
        for (int i = 1, j = 0; i <= n; i++) {
            // 匹配不成功 j = next(j)
            while (j > 0 && s[i] != p[j + 1]) j = next[j];
            // 匹配成功的话，先让 j++，结束本次循环后 i++
            if (s[i] == p[j + 1]) j++;
            // 整一段匹配成功，直接返回下标
            if (j == m) return i - m;
        }

        return -1;
    }
}

复杂度

• 时间复杂度：O(m+n)
• 空间复杂度：O(1)

[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; };

[Ludwig-LL]

思路

这题的一开始想到的就是直接上暴力法，但是这样的效率会比较低。 KMP 的逻辑目前看来还是有点抽象，有一个逻辑推导的过程。 目前还没理解精髓。

代码

目前还写不出，偷抄大佬的代码：

class Solution: def strStr(self, haystack: str, needle: str) -> int:

    # Func: 计算偏移表
    def calShiftMat(st):
        dic = {}
        for i in range(len(st)-1,-1,-1):
            if not dic.get(st[i]):
                dic[st[i]] = len(st)-i
        dic["ot"] = len(st)+1
        return dic

    # 其他情况判断
    if len(needle) > len(haystack):return -1
    if needle=="": return 0

    # 偏移表预处理    
    dic = calShiftMat(needle)
    idx = 0

    while idx+len(needle) <= len(haystack):

        # 待匹配字符串
        str_cut = haystack[idx:idx+len(needle)]

        # 判断是否匹配
        if str_cut==needle:
            return idx
        else:
            # 边界处理
            if idx+len(needle) >= len(haystack):
                return -1
            # 不匹配情况下，根据下一个字符的偏移，移动idx
            cur_c = haystack[idx+len(needle)]
            if dic.get(cur_c):
                idx += dic[cur_c]
            else:
                idx += dic["ot"]

    return -1 if idx+len(needle) >= len(haystack) else idx

时间复杂度

看来应该是比较像是介于O(N) 和O(N^2) 中间。