28. Implement strStr()

題目敘述

Implement strStr().

Return the index of the first occurrence of needle in haystack, or -1 if needle is not part of haystack.

Example 1:

Input: haystack = "hello", needle = "ll"
Output: 2

Example 2:

Input: haystack = "aaaaa", needle = "bba"
Output: -1

Clarification:

What should we return when needle is an empty string? This is a great question to ask during an interview.

For the purpose of this problem, we will return 0 when needle is an empty string. This is consistent to C's strstr() and Java's indexOf().

Constraints:

• haystack and needle consist only of lowercase English characters.

題目翻譯

這個題目其實就是要實作出子字串索引的搜尋函數。找出子字串開頭的索引，如果不包含子字串就回傳 0。

解法解析

基本的解法邏輯參考 Go 的範例，其他語言算是偷懶。因為題目是要實作出函數，所以直接使用程式語言的 built-in 函數，算是偷吃步，正確方式應該像是 Go 的範例。使用類似 Sliding window 的方式去比對。

解法範例

Go

func strStr(haystack string, needle string) int {
    if haystack == needle {
        return 0
    }
    for i := 0; i <= len(haystack)-len(needle); i++ {
        if haystack[i:i+len(needle)] == needle {
            return i
        }
    }

    return -1
}

JavaScript

/**
 * @param {string} haystack
 * @param {string} needle
 * @return {number}
 */
var strStr = function (haystack, needle) {
    if (needle.length === 0) return 0;
    return haystack.indexOf(needle);
};

Kotlin

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

PHP

class Solution
{

    /**
     * @param String $haystack
     * @param String $needle
     * @return Integer
     */
    function strStr($haystack, $needle)
    {
        return strpos($haystack, $needle) !== false ? strpos($haystack, $needle) : -1;
    }
}

Python

class Solution:
    def strStr(self, haystack: str, needle: str) -> int:
        if needle in haystack:
            return haystack.index(needle)
        return -1

Rust

Swift

class Solution {
    func strStr(_ haystack: String, _ needle: String) -> Int {
        guard !needle.isEmpty else { return 0 }
        guard haystack.count >= needle.count else { return -1 }

        let distance = haystack.count - needle.count
        for i in 0...distance {
            let start = haystack.index(haystack.startIndex, offsetBy: i)
            let end = haystack.index(haystack.startIndex, offsetBy: i+needle.count)

            if haystack[start..<end] == needle {
                return start.encodedOffset
            }
        }
        return -1
    }
}