Leetcode 每日一题 28.找出字符串中第一个匹配的下标

问题描述

给定两个字符串 haystack 和 needle，我们需要在 haystack 中找出 needle 字符串的第一个匹配项的下标。如果 needle 不是 haystack 的一部分，则返回 -1。

暴力搜索算法

暴力搜索算法是一种简单直观的字符串匹配方法。它的基本思想是：从 haystack 的每个可能的起始位置开始，检查是否有与 needle 相匹配的子串。

算法步骤

1. 检查空字符串：如果 needle 是空字符串，根据题意返回 0。
2. 获取长度：获取 needle 和 haystack 的长度。
3. 遍历 haystack：遍历 haystack，对于每个可能的起始位置，使用内层循环检查 needle 是否匹配。
4. 字符比较：在内层循环中，比较 haystack 的子串和 needle 的每个字符。
5. 返回结果：如果找到匹配项，返回匹配项的下标；如果遍历完 haystack 都没有找到匹配项，返回 -1。

Java 实现

以下是使用暴力搜索算法解决字符串匹配问题的 Java 实现：

java

class Solution {
    public int strStr(String haystack, String needle) {
        // 如果needle为空字符串，根据题意返回0
        if (needle.isEmpty()) return 0;
        
        // 获取needle和haystack的长度
        int m = needle.length();
        int n = haystack.length();
        
        // 遍历haystack
        for (int i = 0; i <= n - m; i++) {
            // 从当前位置开始比较needle和haystack的子串是否相等
            for (int j = 0; j < m; j++) {
                // 如果不相等，跳出内层循环，继续外层循环
                if (haystack.charAt(i + j) != needle.charAt(j)) {
                    break;
                }
                // 如果相等，继续比较下一个字符
                if (j == m - 1) {
                    return i; // 如果比较完needle的最后一个字符，说明找到了匹配项，返回下标
                }
            }
        }
        
        // 如果遍历完haystack都没有找到匹配项，返回-1
        return -1;
    }
}

代码解释

1. 处理特殊情况：如果 needle 是空字符串，根据题意返回 0。
2. 获取长度：获取 needle 和 haystack 的长度。
3. 遍历 haystack：使用外层循环遍历 haystack，内层循环遍历 needle。
4. 字符比较：在内层循环中，比较 haystack 的当前子串和 needle 的每个字符。
5. 返回结果：如果找到匹配项，返回匹配项的下标；如果遍历完 haystack 都没有找到匹配项，返回 -1。