Leetcode: Two Ptrs: Easy

Technical interviews haven’t changed much, so it’s up to us to upskill and master data structures and algorithms (DSA). Although the LeetCode 75 Study Plan is a great resource, covering just 75 questions to grasp all DSA concepts might not be enough—they tend to favor breadth over depth.

Being a jack of all trades might save us for now, but as time goes by, we might struggle to solve various medium-level problems within a specific topic.

Problem Statement

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: The substring "sad" occurs at indices 0 and 6, but the first occurrence is at index 0.

Example 2

Input: haystack = "leetcode", needle = "leeto"

Output: -1

Explanation: The substring "leeto" does not occur in "leetcode", so the output is -1.

Two-Pointer Technique Solution

Although this problem can be solved with a few lines of code, our goal is to implement it using the two-pointer technique. Below is one such solution:

class Solution:
    def strStr(self, haystack: str, needle: str) -> int:
        # If needle is an empty string, return 0 as per convention.
        if not needle:
            return 0

        for i in range(len(haystack)):
            j = i
            for k in range(len(needle)):
                # Check if we are within the bounds of haystack and characters match.
                if j < len(haystack) and haystack[j] == needle[k]:
                    j += 1
                else:
                    break

                # If we've successfully matched all characters in needle.
                if k == len(needle) - 1:
                    return i

        return -1

Explanation

Outer Loop:

Iterates through each index in haystack, considering it as a potential starting position for needle.
Inner Loop:

For each starting index, it iterates through the characters in needle to verify if the substring in haystack starting at that index matches needle. The loop breaks early if a mismatch is found.
Early Termination:

If the inner loop completes (i.e., all characters in needle have been successfully matched), the function immediately returns the starting index.

Performance Analysis

Time Complexity:

In the worst-case scenario, the outer loop runs n times (where n is the length of haystack) and the inner loop runs up to m times (where m is the length of needle) for each iteration. This results in a worst-case time complexity of O(n * m). However, in most cases, the inner loop terminates early due to mismatches, leading to better average performance.
Space Complexity:

The solution uses only a few extra pointer variables and does not require additional data structures, resulting in a constant space complexity of O(1).

Conclusion

This two-pointer approach provides a clear and intuitive solution for the string matching problem. While it is efficient for many cases, more advanced algorithms—such as the Knuth-Morris-Pratt (KMP) algorithm—can offer better performance in worst-case scenarios when dealing with very large strings.

DEV Community