【Day 83 】2023-05-07 - 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() 定义相符。

[Fuku-L]

代码

class Solution {
    public int strStr(String ss, String pp) {
        int n = ss.length(), m = pp.length();
        char[] s = ss.toCharArray(), p = pp.toCharArray();
        // 枚举原串的「发起点」
        for (int i = 0; i <= n - m; i++) {
            // 从原串的「发起点」和匹配串的「首位」开始，尝试匹配
            int a = i, b = 0;
            while (b < m && s[a] == p[b]) {
                a++;
                b++;
            }
            // 如果能够完全匹配，返回原串的「发起点」下标
            if (b == m) return i;
        }
        return -1;
    }
}

复杂度分析

• 时间复杂度：O((n-m)*m)，其中 n 为原串长度，m 为匹配串长度。
• 空间复杂度：O(1)

[LIMBO42]

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

[RestlessBreeze]

code

class Solution {
public:
    vector<int> buildMatch(string& needle)
    {
        vector<int> match(needle.length());
        match[0] = -1;
        for (int i = 1; i < needle.length(); i++)
        {
            int j = match[i - 1];
            while (j >= 0 && needle[j + 1] != needle[i])
            {
                j = match[j];
            }
            if (needle[j + 1] == needle[i])
            {
                match[i] = j + 1;
            }
            else
            {
                match[i] = -1;
            }
        }
        return match;
    }

    int kmp(string& haystack, string& needle)
    {
        int hlen = haystack.length();
        int nlen = needle.length();
        if (hlen < nlen)
            return -1;
        vector<int> match = buildMatch(needle);
        int hnow = 0;
        int nnow = 0;
        while (hnow < hlen && nnow < nlen)
        {
            if (haystack[hnow] == needle[nnow])
            {
                hnow++;
                nnow++;
            }
            else if (nnow > 0)
            {
                nnow = match[nnow - 1] + 1;
            }
            else
            {
                hnow++;
            }
        }
        return nnow == nlen ? (hnow - nlen) : -1;
    }

    int strStr(string haystack, string needle) {
        return kmp(haystack, needle);
    }
};

[yingchehu]

class Solution:
    def strStr(self, haystack, needle):
        lenA, lenB = len(haystack), len(needle)
        if not lenB:
            return 0
        if lenB > lenA:
            return -1

        for i in range(lenA - lenB + 1):
            if haystack[i:i + lenB] == needle:
                return i
        return -1

[lp1506947671]

class Solution:
    def backtrack(numbers, pre):
        nonlocal res
        if len(numbers) <= 1:
            res.append(pre + numbers)
            return
        for key, value in enumerate(numbers):
            if value not in numbers[:key]:
                backtrack(numbers[:key] + numbers[key + 1:], pre+[value])

    res = []
    if not len(nums): return []
    backtrack(nums, [])
    return res

复杂度分析

• 时间复杂度：由于由 visit 数组的控制使得每递归一次深度-1，因此递归的时间复杂度是N(N - 1) ... 1N∗(N−1)∗...∗1也就是O(N! op(res))，其中 N 是数组长度，op 操作即是昨天说的 res.add 算子的时间复杂度。
• 空间复杂度：O(N * N!)，考虑数组 N 个不重复元素，每一个排列占O(N)，共有 N!个排列。

[chocolate-emperor]

class Solution {
public:
    int strStr(string haystack, string needle) {
        int l1 = haystack.length();
        int l2 = needle.length();
        if(l1<l2)   return -1;

        int res = -1;
        for(int i = 0; i < l1-l2;i++){
            int flag = 1;
            for(int j= 0; j< l2; j++){
                if(needle[j]!=haystack[i+j]){
                    flag = 0;
                    break;
                }
            }
            if(flag)    {
                res = i;
                break;
            }
        }
        return res;
    }
};

[Abby-xu]

class Solution:
    def strStr(self, haystack: str, needle: str) -> int:
        A, B = len(haystack), len(needle)
        if A < B or B==0:
            return -1
        dictNeedle = {}
        dictNeedle[needle] = 1
        left, right = 0, B
        while right<=A:
            if haystack[left:right] in dictNeedle:
                return left
            left+=1
            right+=1
        return -1

[harperz24]

class Solution:
    def strStr(self, haystack: str, needle: str) -> int:
        if len(needle) > len(haystack):
            return -1

        n = len(needle)
        for i in range(len(haystack) - n + 1):
            window = haystack[i: (i + n)]
            if window == needle:
                return i

        return -1

[JasonQiu]

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

[NorthSeacoder]

var strStr = function (haystack, needle) {
    if (needle.length === 0) return 0
    //bf=>暴力算法
    let len = needle.length;
    for (let i = 0; i <= haystack.length - len; i++) {
        let subStr = haystack.slice(i, i + len);
        if (subStr === needle) return i
    }
    return -1
};

[wangqianqian202301]

class Solution:
    def strStr(self, haystack: str, needle: str) -> int:
        for i1 in range(len(haystack) - len(needle) + 1):
            find = False
            for i2 in range(len(needle)):
                if i2 == len(needle) - 1 and needle[i2] == haystack[i1 + i2]:
                    find = True
                if needle[i2] != haystack[i2 + i1]:
                    break

            if find:
                return i1
        return -1

[kangliqi1]

class Solution { public int strStr(String haystack, String needle) { if (needle == null || needle.isEmpty()) { return 0; }

    int m = haystack.length();
    int n = needle.length();
    if (m < n) {
        return -1;
    }

    for (int i=0; i<=m-n; i++) {
        String subStr = haystack.substring(i, i + n);
        if (subStr.equals(needle)) {
            return i;
        }
    }

    return -1;
}

}

[bookyue]

    public int strStr(String haystack, String needle) {
        int len = needle.length();
        int baseN = 26;
        final long MOD = 2147483647;
        long nPlace = 1;
        for (int i = 1; i < len; i++)
            nPlace = (nPlace * baseN) % MOD;

        long needleHash = 0;
        for (int i = 0; i < len; i++)
            needleHash = (baseN * needleHash + needle.charAt(i) - 'a') % MOD;

        long windowHash = 0;
        int left = 0;
        int right = 0;
        while (right < haystack.length()) {
            windowHash = (baseN * windowHash + haystack.charAt(right) - 'a') % MOD;
            right++;

            if (right - left == len) {
                if (needleHash == windowHash && needle.equals(haystack.substring(left, right)))
                    return left;

                windowHash = (windowHash - ((haystack.charAt(left) - 'a') * nPlace) % MOD + MOD) % MOD;
                // X % MOD == (X + MOD) % MOD 是一个模运算法则
                // 因为 windowHash - (txt[left] * nPlace) % MOD 可能是负数
                // 所以额外再加一个 MOD，保证 windowHash 不会是负数
                left++;
            }
        }

        return -1;
    }

[FireHaoSky]

class Solution:
    def strStr(self, haystack: str, needle: str) -> int:
        a=len(needle)
        b=len(haystack)
        if a==0:
            return 0
        i=j=0
        next=self.getnext(a,needle)
        while(i<b and j<a):
            if j==-1 or needle[j]==haystack[i]:
                i+=1
                j+=1
            else:
                j=next[j]
        if j==a:
            return i-j
        else:
            return -1

    def getnext(self,a,needle):
        next=['' for i in range(a)]
        j,k=0,-1
        next[0]=k
        while(j<a-1):
            if k==-1 or needle[k]==needle[j]:
                k+=1
                j+=1
                next[j]=k
            else:
                k=next[k]
        return next

[Lydia61]

28. 实现strStr

思路

经典KMP算法

代码

class Solution {
public:
    int strStr(string s, string p) {
        int n = s.size(), m = p.size();
        for(int i = 0; i <= n - m; i++){
            int j = i, k = 0; 
            while(k < m and s[j] == p[k]){
                j++;
                k++;
            }
            if(k == m) return i;
        }
        return -1;
    }
};

[Jetery]

class Solution {
    public int strStr(String haystack, String needle) {
        for(int i = 0; i < haystack.length(); i++) {
            if (haystack.charAt(i) == needle.charAt(0)) {
                int m = i, n = 0;
                while (n < needle.length() && m < haystack.length()) {
                    if (needle.charAt(n) != haystack.charAt(m)) {
                        break;
                    }
                    m++;
                    n++;
                }
                if (n == needle.length()) {
                    return i;
                }
            }
        }
        return -1;
    }
}

[joemonkeylee]

var strStr = function (haystack, needle) {
    let n = haystack.length
    let m = needle.length
    if (m === 0) return 0

    let next = new Array(m).fill(0)
    for (let i = 1, j = 0; i < m; i++) {
        while (j > 0 && needle[i] !== needle[j]) {
            j = next[j - 1]
        }
        if (needle[i] === needle[j]) {
            j++
        }
        next[i] = j
    }

    for (let i = 0, j = 0; i < n; i++) {
        while (j > 0 && haystack[i] !== needle[j]) {
            j = next[j - 1]
        }
        if (haystack[i] === needle[j]) {
            j++
        }
        if (j === m) {
            return i - m + 1
        }
    }
    return -1
};