LeetCode: Implement strStr()

Problem Description:

Implement strStr().

Returns a pointer to the first occurrence of needle in haystack, or null if needle is not part of haystack.

Solution and Precautions:

Of course, KMP works here. However, the point of the problem is to test your knowledge on using pointers. Just use the brute force way to test each possible substring against the needle with the time complexity of O(m * n) is fine. And reduce the number of loops into n – m – 1, other wise it seems will be TLE for large dataset.

Tips and Divergent thinking:

You don’t have to scan through the haystack and the needle to get their length first. If you use this information, then the coding might be easier, but you should try to code without knowing the length ahead. Of course, if you want to reduce the number of loops, then you at least and only need to know then length of the needle.

Written on May 20, 2013