28. Find the Index of the First Occurrence in a String

Problem

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.

  Example 1:

Input: haystack = "sadbutsad", needle = "sad"
Output: 0
Explanation: "sad" occurs at index 0 and 6.
The first occurrence is at index 0, so we return 0.

Example 2:

Input: haystack = "leetcode", needle = "leeto"
Output: -1
Explanation: "leeto" did not occur in "leetcode", so we return -1.

  Constraints:

• 1 <= haystack.length, needle.length <= 10^4

• haystack and needle consist of only lowercase English characters.

Solution (Java)

class Solution {
    public int strStr(String haystack, String needle) {
        int nl=needle.length();
        int i=0,j=i+nl;
        if (nl==haystack.length())
        {
            if(needle.equals(haystack))
                return 0;
            return -1;
        }
        else if(nl>haystack.length())
            return -1;

        while(j<=haystack.length())
        {
            if(needle.equals(haystack.substring(i,j)))
                return i;
            i++;
            j++;
        }
        return -1;
    }
}

Explain:

nope.

Complexity:

• Time complexity : O(n).
• Space complexity : O(n).

Solution

/**
 * @param {string} haystack
 * @param {string} needle
 * @return {number}
 */
var strStr = function(haystack, needle) {
  var len1 = haystack.length;
  var len2 = needle.length;
  if (!len2) return 0;
  for (var i = 0; i < len1; i++) {
    for (var j = 0; j < len2; j++) {
      if (i + j === len1) return -1;
      if (haystack[i + j] !== needle[j]) break;
      if (j === len2 - 1) return i;
    }
  }
  return -1;
};

Explain:

nope.

Complexity:

• Time complexity : O(n*m).
• Space complexity : O(1).