Implement strStr().

Given two strings needle and haystack, return the index of the first occurrence of needle in haystack, or -1 if needle is not part of haystack.

Clarification:

What should we return when needle is an empty string? This is a great question to ask during an interview.

For the purpose of this problem, we will return 0 when needle is an empty string. This is consistent to C's strstr() and Java's indexOf().

&nbsp;
Example 1:

Input: haystack = "hello", needle = "ll"
Output: 2


Example 2:

Input: haystack = "aaaaa", needle = "bba"
Output: -1


&nbsp;
Constraints:


	1 &lt;= haystack.length, needle.length &lt;= 104
	haystack and needle consist of only lowercase English characters.


class Solution(object):
    def strStr(self, haystack, needle):
        if needle == '':
            return 0
        else:
            return self.search_substring(haystack, needle)

    def search_substring(self, haystack, needle):
        len_substring = len(needle)
        for i in range(len(haystack)):
            if haystack[i: i + len_substring] == needle:
                return i
        return -1
class Solution {
    public int strStr(String haystack, String needle) {
        
        if(needle.length()>haystack.length()) {
            return -1;
        } 
        if(needle.length()==haystack.length()) {
            if(haystack.equals(needle)) {
                return 0;
            }
            return -1;
        }
        
        
        int i=0;
        int j=0;
        while(i<needle.length() && j<haystack.length()) {
            if(needle.charAt(i)==haystack.charAt(j)) {
                i++;
                j++;
                if(i==needle.length()) {
                    return j-needle.length();
                }
            } else {
                j = j-i+1; // backtrack to last pos+1 where there was a probable match
                i=0;
            }
        }
        
        return -1;
    }
}
class Solution {
public:
    int strStr(string haystack, string needle) {
        return haystack.find(needle);
    }
};
var strStr = function(haystack, needle) {
    return haystack.indexOf(needle)
};
Implement strStr()