Approach

This algorithm is very simple and uses a brute force approach to check each substring in haystack:

  • Iterate over each character in haystack and for each starting index, check if the subsequent characters match the needle.

Code

Java
public class Solution {
    public int strStr(String haystack, String needle) {
        if (needle == null || needle.isEmpty()) {
            return 0;
        }

        int n = haystack.length();
        int m = needle.length();

        for (int i = 0; i < n; i++) {
            if (i + m > n) {
                return -1;
            }

            int k = i;
            for (int j = 0; j < m; j++) {
                if (needle.charAt(j) != haystack.charAt(k)) {
                    break;
                }
                if (j == m - 1) {
                    return i;
                }
                k++;
            }
        }

        return -1;
    }
}
Python
class Solution:
    def strStr(self, haystack: str, needle: str) -> int:
        if needle is None or needle == "":
            return 0
        
        n = len(haystack)
        m = len(needle)

        for i in range(n):
            if i + m > n:
                return -1

            k = i
            for j in range(m):
                if needle[j] != haystack[k]:
                    break
                if j == m - 1:
                    return i
                k += 1
        
        return -1

Complexity

  • Time: O(m.n), where n is the length of the haystack and m is the length of the needle. This results from the nested loops where we compare each substring of haystack against needle.
  • Space: O(1)

Lets look at slightly more optimized solution: Optimized Brute Force String Search Algorithm

Pros and Cons

Brute force string matching can be very ineffective, but it can also be very handy in some cases. Just like the sequential search.

It Can Be Very Useful …

  1. Doesn’t require pre-processing of the text – Indeed if we search the text only once we don’t need to pre-process it. Most of the algorithms for string matching need to build an index of the text in order to search quickly. This is great when you’ve to search more than once into a text, but if you do only once, perhaps (for short texts) brute force matching is great!
  2. Doesn’t require additional space – Because brute force matching doesn’t need pre-processing it also doesn’t require more space, which is one cool feature of this algorithm
  3. Can be quite effective for short texts and patterns

It Can Be Ineffective …

  1. If we search more than once the text – As I said in the previous section if you perform the search more than once it’s perhaps better to use another string matching algorithm that builds an index and it’s faster.
  2. It’s slow – In general brute force algorithms are slow and brute force matching isn’t an exception.