攻城獅
Not a programmer 不工程的攻城獅

Not a programmer 不工程的攻城獅

LeetCode Solution, Easy, 28. Implement strStr()

實現子字串索引搜尋函數

攻城獅's photo
攻城獅
·May 8, 2022·

Subscribe to my newsletter and never miss my upcoming articles

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
    }
}

Did you find this article valuable?

Support 攻城獅 by becoming a sponsor. Any amount is appreciated!

Learn more about Hashnode Sponsors
 
Share this

Impressum

As smiple as possible