azl397985856 commented 1 year ago

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

Jetery commented 1 year ago

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

snmyj commented 1 year ago

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

zjsuper commented 1 year ago

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

if needle == haystack:

 #       return 0
    return -1

mayloveless commented 1 year ago

思路

暴力解决，找到第一个匹配字符开始，向后依次匹配，找完为止

代码

var strStr = function(haystack, needle) {
    if (needle.length>haystack.length) return -1;

    for(let i=0;i<haystack.length;i++) {
        if (haystack[i] !== needle[0]) {
            continue;
        }
        let count = 1;
        let idex = i;
        while(count<=needle.length) {
            if (haystack[++idex] !== needle[count++]) {
                break;
            }
        }
        if (count == needle.length+1) {
            return i;
        }
    }

    return -1;
};

复杂度

时间O(m*n) 空间O(1)

Dou-Yu-xuan commented 1 year ago

class Solution: def strStr(self, haystack: str, needle: str) -> int: i = 0 j = 0 len1 = len(haystack) len2 = len(needle)

    while i < len1 and j < len2:
        if haystack[i] == needle[j]:
            i += 1
            j += 1
        else:
            i = i - (j - 1)
            j = 0

    if j == len2:
        return i - j
    else:
        return -1

klspta commented 1 year ago

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

paopaohua commented 1 year ago

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 commented 1 year ago

code

rabin-karp

    public int strStr(String haystack, String needle) {
        int[] map = new int[26];
        for (int i = 0; i < map.length; i++) map[i] = i;

        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 < needle.length(); i++)
            needleHash = (baseN * needleHash + map[needle.charAt(i) - 'a']) % MOD;

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

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

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

        return -1;
    }

Elsa-zhang commented 1 year ago

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

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

tiandao043 commented 1 year ago

思路

kmp，然后看题解可以hash

代码

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

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

        // base value for the rolling hash function
        int a = 26;
        // modulus value for the rolling hash function to avoid overflow
        // long long modulus = pow(2, 31);
        long long modulus = 2147483647;

        // compute the hash of strings haystack[:L], needle[:L]
        long long h = 0, ref_h = 0;
        for (int i = 0; i < needle.length(); i++) {
            h = (h * a + (haystack[i] - 'a')) % modulus;
            ref_h = (ref_h * a + (needle[i] - 'a')) % modulus;
        }
        // cout<<h<<" "<<ref_h<<endl;
        if (h == ref_h) return 0;

        // const value to be used often : a**L % modulus
        long long aL = 1;
        for (int i = 0; i < needle.length(); i++) aL = (aL * a) % modulus;  // 修改就会出错

        for (int start = 1; start < haystack.length() - needle.length() + 1; start++) {
            // compute rolling hash in O(1) time
            h = ((h * a - (haystack[start-1] - 'a') * aL) 
                    + (haystack[start+needle.length()-1] - 'a')) % modulus;
            if (h == ref_h) return start;
        }
        return -1;
    }
};

whoam-challenge commented 1 year ago

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

RestlessBreeze commented 1 year ago

code

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