LeetCode #28. Find the Index of the First Occurrence in a String

This content originally appeared on DEV Community and was authored by Giuseppe

Time Complexity O(n*m)

Outer loop: runs n times (roughly haystack length)
Inside each iteration:

substring() = O(m) time (copies m characters)
.equals() = O(m) time (compares m characters)

Total: n iterations × m work per iteration = n*m

Space Complexity O(m)

The space grows with needle size (m), not haystack size (n).

class Solution {
    public int strStr(String haystack, String needle) {

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

This content originally appeared on DEV Community and was authored by Giuseppe