Find the Index of the First Occurrence in a String

Условие

Дана строка haystack и подстрока needle. Найдите индекс первого вхождения подстроки needle в строке haystack. Если подстрока не найдена, верните -1.

Примеры

Input: haystack = “sadbutsad”, needle = “sad”

Output: 0

Explanation: Подстрока “sad” встречается в строке “sadbutsad” начиная с индекса 0.

Input: haystack = “leetcode”, needle = “leeto”

Output: -1

Explanation: Подстрока “leeto” не встречается в строке “leetcode”.

Решение

fun strStr(haystack: String, needle: String): Int {
    // Если needle пустая строка, возвращаем 0
    if (needle.isEmpty()) return 0
    
    // Длина haystack и needle
    val haystackLength = haystack.length
    val needleLength = needle.length

    // Если needle длиннее haystack, возвращаем -1
    if (needleLength > haystackLength) return -1

    // Проходим по строке haystack
    for (i in 0..(haystackLength - needleLength)) {
        var j = 0
        // Проверяем совпадение каждого символа
        while (j < needleLength && haystack[i + j] == needle[j]) {
            j++
        }
        // Если нашли полное совпадение, возвращаем индекс
        if (j == needleLength) {
            return i
        }
    }
    
    // Если needle не найдено
    return -1
}

Временная сложность

O(n), где n — длина строки haystack. Метод indexOf работает за линейное время.

Пространственная сложность

O(1), так как дополнительное пространство не требуется.