Index of a substring

Question: Write a function that returns the index of where a substring begins within a given string. Return -1 if it doesn't exist.

Related Tags:

Linear Approach

A brute force approach to this problem would be to line up the substring beginning at each character in our string, until a match is found. This approach is simple and easy to understand.

Algorithm Pseudocode

Here's what the algorithm looks by, step-by-step.

  1. Loop through each character c of our str (that fits our substr).
  2. Within this loop, line up each character in the substr, starting with at c.
  3. If any characters do not match, break out and move onto the next character in str.
  4. If we are able to loop through to our last character in substr, return the index of where we started our search in the str.
  5. Otherwise, we have exhausted our search so return -1.

Efficiency

The time complexity is O(mn) where m is the length of the substring and n is the length of the string. Space complexity is O(m+n), simplified to O(n) since the length of our string is always greater than the substring.

Implementation in Java

static int substrIndex(String str, String substr) {

	// Can't have a substring longer than the string itself
	if (substr.length() > str.length()) {
		return -1;
	}

	// iterate through our string until substr that lines up
	char[] strArray = str.toCharArray();
	char[] substrArray = substr.toCharArray();

	// Only up to where our substr can fit
	for (int i = 0; i <= strArray.length - substrArray.length; i++) {
		for (int j = 0; j < substrArray.length; j++) {

			if (strArray[i+j] != substrArray[j]) {
				break;
			}

			// Last char lined up, success!
			if (j == substrArray.length - 1) return i;

		}

	}

	return -1;

}

Came up with a better solution or have a question? Comment below!