A very clean solution, brute-force


  • 58
    S
    int strStr(char *haystack, char *needle) {
            if (!haystack || !needle) return -1;
            for (int i = 0; ; ++i) {
                for (int j = 0; ; ++j) {
                    if (needle[j] == 0) return i;
                    if (haystack[i + j] == 0) return -1;
                    if (haystack[i + j] != needle[j]) break;
                }
            }
        }

  • 0
    Z

    it is amazing


  • 0
    S

    It turns out that "if (!haystack || !needle) return -1;" is not needed


  • 0
    C
    This post is deleted!

  • 0
    C

    Why the following code will "Time Limit Exceeded"
    int strStr(char *haystack, char *needle) {
    if(needle[0]=='\0')
    return 0;
    int j=0;
    for(int i=0;haystack[i]!='\0';i++){
    j=0;
    while(haystack[i+j]==needle[j]){
    if(haystack[i+j]=='\0') return -1;
    if(needle[j]=='\0') return i;
    j++;
    }
    }
    return -1;
    }


  • 0
    A

    my answer use string.assign(string,start,length) seem to a waste of time,but easy to understand

    int strStr(string haystack, string needle) {
        int lengthHasy = haystack.size(),lengthNeed = needle.size();
        string partHays;
        for(int iIndex =0;iIndex <= lengthHasy - lengthNeed;iIndex++)
        {
            partHays.assign(haystack,iIndex,lengthNeed);
            if(partHays == needle)
            return iIndex;
        }
        return -1;
    }

  • 0
    Y
    This post is deleted!

  • -35

    My python code is prettly simple!

    class Solution(object):
    def strStr(self, haystack, needle):
        """
        :type haystack: str
        :type needle: str
        :rtype: int
        """
        index = haystack.find(needle)
        return index
    

  • 0

    no explanation ...


  • 7
    M

    brute-force, with one for-loop

    int strStr(string haystack, string needle) {
        
        if(needle.empty()) return 0;
        if(haystack.empty() || haystack.size()<needle.size()) return -1;
        for(int i=0, j=0; i<haystack.size(); i++){ 
            if(haystack[i] == needle[j]){
                if (j == needle.size()-1) return i-j;
                else j++;
            }
            else if(j){     // previous char are identical but now different
                i = i-j;    // back to the first same character
                j = 0;              
            }
        }
        return -1;
        
    }
    

    ex: haystack = "mississippi" and needle = "issip"

    i=0 j=0 haystack[0]=m needle[0]=i
    i=1 j=0 haystack[1]=i needle[0]=i <-- same char, j++
    i=2 j=1 haystack[2]=s needle[1]=s
    i=3 j=2 haystack[3]=s needle[2]=s
    i=4 j=3 haystack[4]=i needle[3]=i <-- same char
    i=5 j=4 haystack[5]=s needle[4]=p <-- different char, go back to the last same char+1 (i=2)
    i=2 j=0 haystack[2]=s needle[0]=i
    i=3 j=0 haystack[3]=s needle[0]=i
    i=4 j=0 haystack[4]=i needle[0]=i
    i=5 j=1 haystack[5]=s needle[1]=s
    i=6 j=2 haystack[6]=s needle[2]=s
    i=7 j=3 haystack[7]=i needle[3]=i
    i=8 j=4 haystack[8]=p needle[4]=p <-- same char and end of needle => Answer!

  • 0
    B

    NULL and empty,they have different meanings


  • -2
    V

    Is that ok?

    class Solution {
        public:
        	int strStr(string haystack, string needle) {
        		int sl = haystack.length(),nl=needle.length();
        		for (int i = 0; i+nl <= sl;i++)
        			if (haystack.substr(i, nl) == needle)
        				return i;
        		return -1;
        	}
       };

  • 0
    N

    I don't think you know the rule here. your submission is totally wasteful...


  • 0
    G

    Amazing........


  • 0
    S

    naive and KMP

    class Solution {
    public:
        int strStr(string haystack, string needle) {
            //naive alg:time exceed
            /*int n = haystack.size(),m = needle.size();
            for(int i=0;i<n-m+1;i++)
            {
                int j=0;
                while(haystack[i+j] == needle[j] && j<m)
                    j++;
                if(j==m)
                    return i;
            }
            return -1;
            */
            //KMP
            int m = needle.size(),n = haystack.size();
            if(!m)
                return 0;
            vector<int> c = lcps(needle);
            int matchnum = 0;
            for(int i=0;i<n;i++)
            {
                while(matchnum>0 && haystack[i]!=needle[matchnum])
                    matchnum = c[matchnum-1];
                if(haystack[i]==needle[matchnum])
                    matchnum++;
                if(matchnum == m)
                    return i-m+1;
            }
            return -1;
        }
    private:
    vector<int> lcps(string needle)
    {
    	vector<int> c(needle.size());
    	c[0] = 0;
    	int k = 0;
    	for (int i = 1; i<needle.size(); i++)
    	{
    		while (k > 0 && needle[k] != needle[i])
    			k = c[k-1];
    		if (needle[i] == needle[k])
    			k++;
    		c[i] = k;
    	}
    	return c;
    }
        
    };

Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.