Implement strStr()

Problem

Given two strings needle and haystack, return the index of the first occurrence of needle in haystack, or -1 if needle is not part of haystack.

Example 1:

Input: haystack = "sadbutsad", needle = "sad"
Output: 0
Explanation: "sad" occurs at index 0 and 6.
The first occurrence is at index 0, so we return 0.

Example 2:

Input: haystack = "leetcode", needle = "leeto"
Output: -1
Explanation: "leeto" did not occur in "leetcode", so we return -1.

Constraints:

  • 1 <= haystack.length, needle.length <= 10^4
  • haystack and needle consist of only lowercase English characters.

Solution

O(n * m) time complexity.

class Solution {
    public int strStr(String haystack, String needle) {
        for (var h = 0; h <= haystack.length() - needle.length(); h++) {
            var ok = true;
            for (var n = 0; n < needle.length(); n++) {
                var ch = haystack.charAt(h + n);
                var cn = needle.charAt(n);
                if (ch != cn) {
                    ok = false;
                    break;
                }
            }
            if (ok) {
                return h;
            }
        }
        return -1;
    }
}

Recent posts from blogs that I like

Painting and Photography: Is it art?

Degas' photos of women bathing, Gérôme supporting photography as a fine art, Pierre Bonnard's snaps of Marthe, and the extreme realism of Ellen Altfest.

via The Eclectic Light Company

How often do LLMs snitch? Recreating Theo's SnitchBench with LLM

via Simon Willison

The virtue of unsynn

via fasterthanlime