010-实现 strStr() (Implement strStr())

题目描述

实现 strStr() 函数。

给你两个字符串 haystack 和 needle，请你在 haystack 字符串中找出 needle 字符串出现的第一个位置（下标从 0 开始）。如果不存在，则返回 -1。

说明：

当 needle 是空字符串时，我们应当返回什么值呢？这是一个在面试中很好的问题。

对于本题而言，当 needle 是空字符串时我们应当返回 0。这与 C 语言的 strstr() 以及 Java 的 indexOf() 定义相符。

示例

输入：haystack = "hello", needle = "ll"
输出：2

输入：haystack = "aaaaa", needle = "bba"
输出：-1

输入：haystack = "", needle = ""
输出：0

解题思路

使用滑动窗口法，遍历 haystack 字符串，对于每个位置，检查从该位置开始的子串是否与 needle 匹配。这种方法简单直观，适合面试中使用。

JavaScript 解决方案

/**
 * @param {string} haystack
 * @param {string} needle
 * @return {number}
 */
const strStr = (haystack, needle) => {
    // 如果 needle 为空，返回 0
    if (needle === "") return 0;
    
    const haystackLen = haystack.length;
    const needleLen = needle.length;
    
    // 如果 needle 长度大于 haystack，不可能匹配
    if (needleLen > haystackLen) return -1;
    
    // 遍历 haystack 的每个可能起始位置
    for (let i = 0; i <= haystackLen - needleLen; i++) {
        let match = true;
        
        // 检查从位置 i 开始的子串是否匹配
        for (let j = 0; j < needleLen; j++) {
            if (haystack[i + j] !== needle[j]) {
                match = false;
                break;
            }
        }
        
        if (match) {
            return i;
        }
    }
    
    return -1;
};

复杂度分析

时间复杂度：O((n-m+1) × m)，其中 n 是 haystack 长度，m 是 needle 长度
空间复杂度：O(1)，只使用了常数额外空间

测试用例

// 测试函数
const testStrStr = () => {
    const testCases = [
        {
            haystack: "hello",
            needle: "ll",
            expected: 2
        },
        {
            haystack: "aaaaa",
            needle: "bba",
            expected: -1
        },
        {
            haystack: "",
            needle: "",
            expected: 0
        },
        {
            haystack: "hello",
            needle: "",
            expected: 0
        },
        {
            haystack: "hello",
            needle: "hello",
            expected: 0
        },
        {
            haystack: "hello",
            needle: "world",
            expected: -1
        },
        {
            haystack: "mississippi",
            needle: "issip",
            expected: 4
        },
        {
            haystack: "a",
            needle: "a",
            expected: 0
        },
        {
            haystack: "abc",
            needle: "c",
            expected: 2
        },
        {
            haystack: "abc",
            needle: "abcd",
            expected: -1
        }
    ];

    testCases.forEach((testCase, index) => {
        const result = strStr(testCase.haystack, testCase.needle);
        const passed = result === testCase.expected;
        console.log(`测试用例 ${index + 1}: ${passed ? '通过' : '失败'}`);
        console.log(`输入: haystack = "${testCase.haystack}", needle = "${testCase.needle}"`);
        console.log(`期望: ${testCase.expected}, 实际: ${result}\n`);
    });
};

// 运行测试
testStrStr();

关键点总结

边界处理：空字符串 needle 返回 0
长度检查：needle 长度大于 haystack 时返回 -1
滑动窗口：遍历每个可能的起始位置
字符匹配：逐字符比较子串
提前返回：找到第一个匹配位置立即返回

总结

这道题考察了以下重点：

字符串匹配：理解字符串匹配的基本算法
滑动窗口：使用滑动窗口遍历字符串
边界处理：对各种边界情况的考虑
算法优化：虽然可以使用 KMP 等高级算法，但简单解法在面试中更实用

滑动窗口法是最直观的解法，时间复杂度为 O((n-m+1) × m)，空间复杂度为 O(1)。在实际面试中，建议先提出这种简单解法，然后可以讨论 KMP 等优化算法。

010-实现 strStr() (Implement strStr())

On this page