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

First, make some judgments. If the substring is empty, it returns 0, and if the length of the substring is greater than the length of the parent string, it returns -1.

Then start to traverse the parent string, here it is not necessary to traverse the entire parent string, but to traverse to the remaining position equal to the length of the substring, which can improve the computational efficiency.

Then for each character, traverse the substring again, compare the corresponding characters one by one, if there are unequal positions in the corresponding position, then jump out of the loop, if there is no jump out of the loop, then the substring appears, then return Starting position.

Code

Java

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);
		}
	}

}

All Problems

All Solutions