Implement strStr() Solution in Java

Problem Description

The classic “strStr()” problem is like trying to find your keys in a messy room. Given a “haystack” (the big string) and a “needle” (the small string), you need to find the first occurrence of the needle in the haystack. If you can’t find it, return -1. It’s akin to asking a friend to find a specific sock in a laundry basket full of mismatched socks.

Code Solution

class Solution {
  public int strStr(String haystack, String needle) {
    final int m = haystack.length();
    final int n = needle.length();

    for (int i = 0; i < m - n + 1; ++i)
      if (haystack.substring(i, i + n).equals(needle))
        return i;

    return -1;
  }
}

Approach

The approach is straightforward: loop through the "haystack" and check every substring of the same length as the "needle". If a match is found, return the starting index. If the loop finishes without finding it, return -1. It’s like checking every room in your house until you find that elusive sock!

Time and Space Complexity

Time Complexity

O((m - n + 1) * n) in the worst case, where m is the length of the haystack and n is the length of the needle. For each position in the haystack, we may need to check up to n characters.

Space Complexity

O(1), as we are using a constant amount of space regardless of the input size.

Real-World Example

Imagine you’re at a party, trying to find your friend named "John" in a crowd. You scan each face (the haystack) until you spot him (the needle). If you don’t find him after checking everyone, you just give up and go home. This is exactly what our code does!