Implement strStr().

Returns the index of the first occurrence of needle in haystack, or -1 if needle is not part of haystack.

 

New version: 4ms

1 class Solution { 2 public: 3     int strStr(string haystack, string needle) { 4         int result = 0; 5         int lenN = needle.size(), lenH = haystack.size(); 6         if(lenN == 0 && lenH == 0) return 0; 7         if(lenN == 0) return 0; 8         if(lenH < lenN) return -1; 9         10         for(int i = 0; i <= lenH - lenN; i++){11             if(haystack[i] == needle[0]){12                 int index = 0, move = i;13                 while(move < lenH && index < lenN && haystack[move] == needle[index]){14                     move++;15                     index++;16                 }17                 if(index == lenN) return i;18             }19         }20         return -1;21     }22 };

 

Analyse: Pay special attention to when the length of haystack is less  than that of needle, and the case that needle is empty.

1 class Solution { 2 public: 3     int strStr(string haystack, string needle){ 4         int index = -1; 5         if(haystack.length() < needle.length()) return index; 6         else if(needle.length() == 0) return 0; 7          8         for(int j = 0; j <= haystack.length() - needle.length(); j++){ 9             int index_needle = 0;10             if(haystack[j] == needle[index_needle]){11                 index = j;12                 for(int k = 1; k < needle.length(); k++){13                     if(haystack[j+k] != needle[index_needle+k]){14                         index = -1;15                         break;16                     }17                 }18             }19             if(index >= 0) return index;20         }21         return index;22     }23 };