Implement strStr() solution using TypeScript

This post outlines my TypeScript solution to the "Implement strStr()" question on LeetCode.

Algorithm: The solution finds a substring by doing the following:

• Find the first character of the needle in the haystack.
• Compare the following characters in the haystack with the following characters in the needle.
• If they all match, return the index of the first matched character in the haystack.
• If not, backtrack to the first matched character in the haystack and repeat the above steps.

Time Complexity: Because the algorithm will iterate the characters in the haystack one time, but may need to backtrack the number of characters in the needle for each character in the haystack, the time complexity is O((h - n) * n) where h represents the number of characters in the haystack and n represents the number of characters in the needle. The time complexity of this solution could be improved by using rolling hash.

Space Complexity: Because the solution will use a constant amount of space, the space complexity is O(1).

/**
 * Implement strStr()
 * Return the index of the first occurrence of needle 
 * in haystack, or -1 if needle is not part of haystack.
 *
 * Time Complexity: O((h - n) * n)
 * Space Complexity: O(1)
 *
 * strStr("hello", "ll") // 2
 * strStr("aaaaa", "bba") // -1
 */
function strStr(haystack: string, needle: string): number {
    let ptr1 = 0; // haystack pointer
    let ptr2 = 0; // needle pointer
    
    // handle edge cases
    if (haystack === needle || needle.length === 0) {
        return 0;
    }
    if (needle.length > haystack.length) {
        return -1;
    }

    while (ptr1 < haystack.length) {
        // find the first character of the needle in the haystack
        while (haystack[ptr1] !== undefined && haystack[ptr1] !== needle[ptr2]) {
            ptr1 += 1;
            ptr2 = 0;
        }
        
        // check if the haystack chars that follow match the needle chars
        while (haystack[ptr1] !== undefined && haystack[ptr1] === needle[ptr2]) {
            ptr1 += 1;
            ptr2 += 1;
        }
        
        // the entire needle was found
        if (ptr2 === needle.length) {
            return ptr1 - ptr2;
        }

        // didn't find needle, so backtrack
        ptr1 = 1 + ptr1 - ptr2;
        ptr2 = 0;
    }
    
    return -1;
}