LeetCode_28. Implement strStr()

28. Implement strStr()

Easy

Implement strStr().

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

package leetcode;

public class ImplementStrStr {
	@org.junit.Test
	public void test() {
		String haystack1 = "hello";
		String needle1 = "ll";
		String haystack2 = "aaaaa";
		String needle2 = "bba";
		System.out.println(strStr(haystack1, needle1));
		System.out.println(strStr(haystack2, needle2));
	}

	public int strStr(String haystack, String needle) {
		char[] source = haystack.toCharArray();
		int sourceOffset = 0;
		int sourceCount = haystack.length();
		char[] target = needle.toCharArray();
		int targetOffset = 0;
		int targetCount = needle.length();
		int fromIndex = 0;
		if (fromIndex >= sourceCount) {
			return (targetCount == 0 ? sourceCount : -1);
		}
		if (fromIndex < 0) {
			fromIndex = 0;
		}
		if (targetCount == 0) {
			return fromIndex;
		}

		char first = target[targetOffset];
		int max = sourceOffset + (sourceCount - targetCount);

		for (int i = sourceOffset + fromIndex; i <= max; i++) {
			/* Look for first character. */
			if (source[i] != first) {
				while (++i <= max && source[i] != first)
					;
			}

			/* Found first character, now look at the rest of v2 */
			if (i <= max) {
				int j = i + 1;
				int end = j + targetCount - 1;
				for (int k = targetOffset + 1; j < end && source[j] == target[k]; j++, k++)
					;

				if (j == end) {
					/* Found whole string. */
					return i - sourceOffset;
				}
			}
		}
		return -1;
	}
}