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

Задача

Даны две строки needle (игла) и haystack (стог сена). Верните индекс первого вхождения needle в haystack или -1, если needle не является частью haystack.

Примеры

Пример 1

Input: haystack = "sadbutsad", needle = "sad"
Output: 0

Пояснение

“sad” встречается по индексам 0 и 6. Первое вхождение — индекс 0.

Пример 2

Input: haystack = "leetcode", needle = "leeto"
Output: -1

Пояснение

“leeto” не встречается в “leetcode”.

Решение

Решение

/**
 * Временная сложность: O((N - M) * M), где N — длина haystack, M — длина needle.
 * В худшем случае (например, "aaaaaab" и "aab") мы почти для каждого символа проверяем M символов.
 * 
 * Пространственная сложность: O(1)
 * Мы используем только несколько переменных для индексов, дополнительная память не зависит от размера строк.
 */
var strStr = function(haystack, needle) {
    if (needle.length === 0) return 0;
 
    // Проходим только до того места, где needle еще может поместиться
    for (let i = 0; i <= haystack.length - needle.length; i++) {
        let j = 0;
 
        // Внутренний цикл проверяет совпадение
        while (j < needle.length && haystack[i + j] === needle[j]) {
            j++;
        }
 
        // Если дошли до конца needle, значит нашли полное совпадение
        if (j === needle.length) {
            return i;
        }
    }
 
    return -1;
};

Решение 2 (мое)

var strStr = function(haystack, needle) {
    let match = 0;
 
    for (let i = 0; i < haystack.length; i++) {
        console.log(haystack[i], needle[match]);
 
        if (haystack[i] === needle[match]) {
            match++;
 
            if (match === needle.length) {
                return i + 1 - match;
            } else {
                continue;
            }
        } else {
            i = i - match;
            match = 0;
        }
 
        const remainingLength = haystack.length - i - 1;
        const requiredLength = needle.length - match - 1;
 
        if (remainingLength < requiredLength) {
            return -1;
        }
 
    }
 
    return -1;
};