29-Implement-strStr.md

Implement strStr()

Problem Link

https://leetcode.com/problems/implement-strstr/

---

Pattern

• String
• Pattern Matching

---

Approach

Slide window through haystack and compare with needle.

---

Time Complexity

O(n * m)

Space Complexity

O(1)

---

Java Solution

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