Implement strStr().
Returns a pointer to the first occurrence of needle in haystack, or null if needle is not part of haystack.
I wrote that function before in practice without knowing anything about strStr(), so I have a pretty clear brute-force solution in my mind.
1 class Solution { 2 public: 3 char *strStr(char *haystack, char *needle) { 4 char *i = haystack; 5 char *j = needle; 6 int k = 0, m = 0; 7 if (*j==‘\0‘)return haystack; 8 while (*i != ‘\0‘){ 9 while (*(i+k)!=‘\0‘ && *(j+m)!=NULL && *(i+k) == *(j+m)){ 10 k++; 11 m++; 12 } 13 if (k!=0 && m!= 0){ 14 if (*(j+m) == ‘\0‘){ 15 return i; 16 }else{ 17 k=0;m=0; 18 } 19 } 20 i++; 21 } 22 return NULL; 23 } 24 };
Not very clean, with some unnecessary variable but express my thought well,
unfortunately it‘s Time Limit Exceeded, means we can still do
some optimize.
Some people says using KMP can definitely solve the problem,
but its too hard to code(for me). I don‘t think people will ask to write KMP
during an interview.
Then I find this thread the trick is, in fact we should aways only
iterate N-M+1 times.
my AC version:
1 class Solution { 2 public: 3 char *strStr(char *haystack, char *needle) { 4 char *i = haystack; 5 char *j = needle; 6 char *l = haystack; 7 int k = 0; 8 if (!*j)return haystack; 9 10 while (*++j){ 11 l++; 12 } 13 j = needle; 14 15 while (*l){ 16 while (*(i+k) && *(j+k) && *(i+k) == *(j+k)){ 17 k++; 18 } 19 if (k!=0){ 20 if (!*(j+k)){ 21 return i; 22 }else{ 23 k=0; 24 } 25 } 26 i++; 27 l++; 28 } 29 return NULL; 30 } 31 };
Implement strStr(),布布扣,bubuko.com
原文：http://www.cnblogs.com/agentgamer/p/3674571.html