Implement strStr() – LeetCode

strstr (a.k.a find sub string), is a useful function in string operation. You task is to implement this function. For a given source string and a target string, you should output the “first” index(from 0) of target string in source string.

If target is not exist in source, just return -1.
For example, if source=”source” and target=”target”, return -1. If source=”abcdabcdefg” and target=”bcd”, return 1.

Challenge: O(n) time.

Clarification

Q: Do I need to implement KMP Algorithm in an interview?
A: – Not necessary. When this problem occurs in an interview, the interviewer just want to test your basic implementation ability.

O(nm) runtime, O(1) space – Brute force:

You could demonstrate to your interviewer that this problem can be solved using known efficient algorithms such as Rabin-Karp algorithm, KMP algorithm, and the Boyer- Moore algorithm. Since these algorithms are usually studied in an advanced algorithms class, it is sufficient to solve it using the most direct method in an interview – The brute force method.

The brute force method is straightforward to implement. We scan the needle with the haystack from its first position and start matching all subsequent letters one by one. If one of the letters does not match, we start over again with the next position in the haystack.

The key is to implement the solution cleanly without dealing with each edge case separately.

Code

Share on FacebookShare on Google+Tweet about this on TwitterShare on LinkedInShare on RedditShare on StumbleUponEmail this to someoneShare on TumblrDigg this

Leave a Reply

Your email address will not be published. Required fields are marked *

You may use these HTML tags and attributes: <a href="" title=""> <abbr title=""> <acronym title=""> <b> <blockquote cite=""> <cite> <code class="" title="" data-url=""> <del datetime=""> <em> <i> <q cite=""> <strike> <strong> <pre class="" title="" data-url=""> <span class="" title="" data-url="">