[Leetcode] implement strStr() (C++)

Github leetcode 我的解题仓库 https://github.com/interviewcoder/leetcode

题目：

Implement strStr().

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

Update (2014-11-02):
The signature of the function had been updated to return the index instead of the pointer. If you still see your function signature returns a char * or String, please click the reload button to reset your code definition.

Tag:

String; Two Pointers

体会：

这道题是字符串的匹配问题，目前还只会朴素的逐步方法，但是这道题还有KMP解法，和Boyer-Moore的解法，目前还没有掌握。

先把笔记放到这里，以后再来解决吧。

1. KMP算法

2. Boyer-Moore算法

 class Solution {

 public:

     int strStr(char *haystack, char *needle) {

         int i = ;  // index under examine in haystack

         int j = ;  // index under examine in needle

         while (haystack[i] && needle[j]) {

             if (haystack[i] == needle[j]) {

                 i++;

                 j++;

             } else {

                 // roll back:

                 // reset haystack index back to (i - j + 1), since in current examine

                 // start index in haystack is (i - j)

                 i = i - j + ;

                 // reset needle back to its beginning

                 j = ;

             }

         }

         // if haystack ends but needle not ends,

         // we know needle is not in the haystack, then return -1.

         return (needle[j]) ? - : (i - j);

     }

 };

巴特西

[Leetcode] implement strStr() (C++)

最新文章

热门文章