Leetcode: Implement strStr() (4ms)

Implement strStr().

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

Subscribe to see which companies asked this question

Hide Tags

 Two Pointers String

Show Similar Problems

------------------------------------------------------------

------------------------------------------------------------

Using two pointers, but note following cases:

1. haystack = "mississippi", 

        needle = "issip";

2. haystack="aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaab"

    needle=    "aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaa"

3. when needle is longer than haystack. 

/////////////////////////////////////////////////////////////////////////////

//codes

class Solution {

 public:

        int strStr(string haystack, string needle) {

               //check input

               int len = haystack.size(), i = 0, j = 0;

               if (needle.size() == 0) return 0;

               if (len == 0 || needle.size() == 0 || len<needle.size())return -1;//case 3

               while (i<len - needle.size() + 1){ //case 2

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

                            i++;

                            continue;

                      }

                      //check needle

                      int k = i;

                      while (j<needle.size()){

                            if (haystack[k] != needle[j]){

                                   i++;//i=k;//case 1

                                   j = 0;

                                   break;

                            }

                            else{

                                   if (j == needle.size() - 1)return i;

                                   k++;

                                   j++;

                            }

                      }

               }

               return -1;

        }

 };

////////////////////////////////////////////////////////////////////////////////////////////////////////////////////

the whole codes

#include <iostream>
using namespace std;
#include <vector>
#include <string>

class solution{
  public:
  int strstr(string& s1, string& s2){
    for(int i=0;i<s1.size();i++){
      if (s1[i]==s2[0]){
        for (int j=0;j<s2.size();j++){
          if (i+j>=s1.size() || s1[i+j]!=s2[j])break;
          if(j==s2.size()-1) return i;
        }
        
      } 
    }
    return -1;
  }
  
  
  
};

// To execute C++, please define "int main()"
int main() {
  
  solution s;
  string s1={"acbccc"}, s2={"cccc"},s3={"abc"};
  vector<string> ss;
  ss.push_back(s1);
  ss.push_back(s2);
  ss.push_back(s3);
  int res=s.strstr(s1, s2);
  cout<<"the results is: "<<res <<"\n";
  cout<<ss[0]<<ss[1] <<ss[2]<<"\n";
  

  return 0;
}