Question

Formatted question description: https://leetcode.ca/all/28.html

28	Implement strStr()

Implement strStr().

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

Example 1:

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

Example 2:

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

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().

Algorithm

To solve this problem, we need to make the following judgments:

If the substring is empty, return 0
If the length of the substring is greater than the length of the parent string, return -1.

Next, we will traverse the parent string. However, we don’t need to traverse the entire parent string. We can stop traversing when there are only len(parent_str) - len(substring) + 1 characters left. This can improve computational efficiency.

For each character in the parent string, we will traverse the substring again and compare the corresponding characters. If there is an unequal position in the corresponding position, we break out of the loop. If the substring is found, we return the starting position.

Code

public class Implement_strStr {

	public static void main(String[] args) {
		String a = "abc";
		String b = "abc";

		System.out.println(a == b);
	}


	public class Solution {
	    // @para: h for haystack, n for needle
	    public int strStr(String h, String n) {
	        if(h == null || n == null || h.length() < n.length()) {
	            return -1;
	        }

	        int window = n.length();
	        for(int i = 0; i + window - 1 < h.length(); i++) {

	            if(h.substring(i, i + window).startsWith(n)) {
	                return i;
	            }
	        }

	        return -1;
	    }
	}

	public class Solution_brute_force {
	    // @para: h for haystack, n for needle
	    public int strStr(String h, String n) {
	        if(h == null || n == null || h.length() < n.length()) {
	            return -1;
	        }

	        for(int i = 0; i < h.length(); i++) {
	            if(h.substring(i).startsWith(n)) {
	                return i;
	            }
	        }

	        return -1;
	    }
	}

	// ;p
	class Solution_ha {
		public int strStr(String haystack, String needle) {
			return haystack.indexOf(needle);
		}
	}

}

// OJ: https://leetcode.com/problems/implement-strstr/
// Time: O(MN)
// Space: O(1)
class Solution {
public:
    int strStr(string haystack, string needle) {
        if (needle.size() > haystack.size()) return -1;
        for (int i = 0; i <= haystack.size() - needle.size(); ++i) {
            int j = 0;
            for (; j < needle.size() && haystack[i + j] == needle[j]; ++j);
            if (j == needle.size()) return i;
        }
        return -1;
    }
};

class Solution:
    def strStr(self, haystack: str, needle: str) -> int:
        n, m = len(haystack), len(needle)
        for i in range(n - m + 1):
            if haystack[i : i + m] == needle:
                return i
        return -1

############

class Solution(object):
  def strStr(self, haystack, needle):
    """
    :type haystack: str
    :type needle: str
    :rtype: int
    """
    if len(haystack) == len(needle):
      if haystack == needle:
        return 0
      else:
        return -1

    for i in range(0, len(haystack)):
      k = i
      j = 0
      while j < len(needle) and k < len(haystack) and haystack[k] == needle[j]:
        j += 1
        k += 1
      if j == len(needle):
        return i
    return -1 if needle else 0

28 - Implement strStr()

Question

Algorithm

Code

All Problems

All Solutions

Welcome to Subscribe On Youtube

Question

Algorithm

Code

All Problems

All Solutions