【Day 84 】2023-01-23 - 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() 定义相符。

[FlipN9]

class Solution {
    public int strStr(String str, String pat) {
        char[] text = str.toCharArray();
        char[] patn = pat.toCharArray();

        int tLen = text.length;
        int pLen = patn.length;

        if (tLen < pLen) return -1;

        int tStartIdx = 0;
        int pIdx = pLen - 1;               
        int tIdx = tStartIdx + pIdx;

        while (tIdx < tLen) {
            while (pIdx >= 0 && text[tIdx] == patn[pIdx]) { 
                pIdx--;
                tIdx--;
            }
            if (pIdx < 0) return tStartIdx;
            while (pIdx >= 0 && text[tIdx] != patn[pIdx]) {
                pIdx--;
            }
            tStartIdx = tIdx - pIdx;
            pIdx = pLen - 1;
            tIdx = tStartIdx + pIdx;
        }
        return -1;
    }
}

[snmyj]

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

[tiandao043]

class Solution {
public:
    vector<int> getNext(string needle){   
        int i=0,j=-1;     
        int n=needle.length();
        vector<int> next(n+1,-1);
        while(i<n){
            if(j==-1 || needle[i]==needle[j]){
                i++;j++;
                next[i]=j;
            }
            else{
                j=next[j];
            }
        }
        return next;
    }
    int strStr(string haystack, string needle) {
        if(needle.empty())return 0;
        int i=0,j=0,flag=false;
        int m=haystack.length();
        int n=needle.length();
        vector<int> next=getNext(needle);
        // next[0]=n;
        for(auto& v:next){
            cout<<v<<endl;
        }
        while(i<m && j<n){
            flag=true;
            // cout<<"!"<<endl;
            if(j==-1||haystack[i]==needle[j]){
                i++;j++;
            }
            else{
                j=next[j];
            }
        }
        // cout<<j<<" "<<n<<endl;
        if(j==n){
            // cout<<i-n+1<<endl;
            // if(m==0)return-1;
            // else if(n>m)return -1;
            return i-n;
        }
        else{
            return -1;
        }
    }
};

[paopaohua]

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

[mayloveless]

思路

kmp

代码

/**
 * @param {string} haystack
 * @param {string} needle
 * @return {number}
 */
var strStr = function(haystack, needle) {
    if (needle.length>haystack.length) return -1;

    const n = haystack.length;
    const m = needle.length;
    const s = " " + haystack;
    const p = " " + needle;

    // 找模式串中最大长度的相同前缀和后缀
    const next = new Array(m + 1).fill(0);
    for (let i = 2, j = 0; i <= m; i++) {
        while (j > 0 && p[i] !== p[j + 1]) {
            j = next[j];
        }
        // 遇到重复
        if (p[i] == p[j + 1]) {
            j++;
        }
        next[i] = j;
    }
    for (let i = 1, j = 0; i <= n; i++) {
        // i是终点，j是个数
        while (j > 0 && s[i] != p[j + 1]) {
            // j移动到next，可以不从0开始
            j = next[j];
        }
        if (s[i] == p[j + 1]) {
            j++;
        }
        // 长度够了
        if (j == m) {
            return i - m;
        }
    }
    return -1;
};

复杂度

时间O（m+n） 空间O（m）

[bookyue]

code

    public int strStr(String haystack, String needle) {
        int m = needle.length();
        int[] next = new int[m];

        for (int i = 1, j = 0; i < m; i++) {
            while (j > 0 && needle.charAt(i) != needle.charAt(j))
                j = next[j - 1];

            if (needle.charAt(i) == needle.charAt(j))
                j++;

            next[i] = j;
        }

        for (int i = 0, j = 0; i < haystack.length(); i++) {
            while (j > 0 && haystack.charAt(i) != needle.charAt(j))
                j = next[j - 1];

            if (haystack.charAt(i) == needle.charAt(j))
                j++;

            if (j == m) return i - m + 1;
        }

        return -1;
    }

[klspta]

class Solution {
    public int strStr(String s, String p) {
        if(s == null || "".equals(s)){
            return 0;
        }

        int n = s.length();
        int m = p.length();

        int[] ne = new int[m + 1];

        for(int i = 2, j = 0; i <= m; i++){
            while(j > 0 && p.charAt(i - 1) != p.charAt(j)){
                j = ne[j];
            }
            if(p.charAt(i - 1) == p.charAt(j)){
                j++;
            }
            ne[i] = j;
        }

        for(int i = 1, j = 0; i <= n; i++){
            while(j > 0 && s.charAt(i - 1) != p.charAt(j)){
                j = ne[j];
            }
            if(s.charAt(i - 1) == p.charAt(j)){
                j++;
            }
            if(j == m){
                return i - m;
            }
        }

        return -1;
    }
}

[azl397985856]

💪🏻 加油

[RestlessBreeze]

code

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

[Ryanbaiyansong]

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

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

[whoam-challenge]

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