# A very clean solution, brute-force

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

• it is amazing

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

• This post is deleted!

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

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

• This post is deleted!

• 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
``````

• no explanation ...

• 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!``````

• NULL and empty,they have different meanings

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

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

• Amazing........

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

};``````

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