Daily LeetCode Challenge - 28. Find the Index of the First Occurrence in a String

Problem From.

https://leetcode.com/problems/find-the-index-of-the-first-occurrence-in-a-string/

오늘 문제는 haystack 안에 needle 이 들어있다면 그 시작 인덱스를 반환하고 없다면 -1을 반환하는 문제였다.

Sliding window 를 사용하여, haystack 에서 needle 의 범위만큼을 index 를 1 씩 증가시켜가면서 검사하여 들어있다면 시작 인덱스를 반환하였다.

class Solution {
    fun strStr(haystack: String, needle: String): Int {
        val total = needle.length
        val part = haystack.length

        for (start in 0..part - total) {
            for (i in 0..total - 1) {
                if (needle[i] != haystack[start + i]) {
                    break
                }
                if (i == total - 1) {
                    return start
                }
            }
        }

        return -1
    }
}

위 풀이의 시간 복잡도는 O(N*M) 이 된다.

더 간단한 풀이로는 코틀린의 내장함수를 사용하여 풀 수 있다.

class Solution {
    fun strStr(haystack: String, needle: String): Int {
        return haystack.indexOf(needle)
    }
}