每日一算法(找到字符串中第一个匹配项的下标)

给你两个字符串 haystack 和 needle ，请你在 haystack 字符串中找出 needle 字符串的第一个匹配项的下标（下标从 0 开始）。如果 needle 不是 haystack 的一部分，则返回 -1 。

• 示例 1：

  • 输入：haystack = “sadbutsad”, needle = “sad”
  • 输出：0
  • 解释：“sad” 在下标 0 和 6 处匹配。
  • 第一个匹配项的下标是 0 ，所以返回 0 。

• 示例 2：

  • 输入：haystack = “leetcode”, needle = “leeto”
  • 输出：-1
  • 解释：“leeto” 没有在 “leetcode” 中出现，所以返回 -1 。

一、最简单解法(indexOf())

• 使用Java自带的indexOf()方法 查找当needle子串在haystack中第一次出现的位置索引，找不到返回-1

  /**
     *
     * @param haystack 要搜索的原始字符串
     * @param needle   要检查的子字符串
     * @return 存在返回该子串的索引位置，不存在返回-1
     */
    public static int strStrIndexOf(String haystack, String needle) {
        return haystack.indexOf(needle);
    }

二、String中的startsWith()解法

• 思路:先将原始参数跟指定参数判断它的有效性，然后通过循环遍历找到该子串的位置,在给定字符串中检查是否以指定的子字符串开头。 如果是，则返回该子字符串在原始字符串中的起始位置索引；如果不是或输入参数无效，则返回 -1。

   /**
     *
     * @param haystack 要搜索的原始字符串
     * @param needle   要检查的子字符串
     * @return 存在返回该子串的索引位置，不存在返回-1
     */
    public static int startStrWith(String haystack, String needle) {
        if (haystack.isEmpty() || needle.isEmpty() || haystack.length() < needle.length()) {
            return -1;
        }
        //遍历原始字符串，检查是否以子字符串开头
        for (int i = 0; i <= haystack.length() - needle.length(); i++) {
            //使用 startsWith 方法检查从当前位置开始的子字符串是否与指定的子字符串相匹配
            if (haystack.startsWith(needle, i)) {
                return i;
            }
        }
        return -1;
    }

三、String中的substring()解法

• 思路:使用 startStrSub()方法，用于在一个字符串（称为 haystack）中查找另一个字符串（称为 needle）的第一个出现位置的起始索引
  代码如下（示例）：

  /**
     * 思路:使用  startStrSub()方法，用于在一个字符串（称为 haystack）中查找另一个字符串（称为 needle）的第一个出现位置的起始索引
     *
     * @param haystack 要搜索的原始字符串
     * @param needle   要检查的子字符串
     * @return 存在返回该子串的索引位置，不存在返回-1
     */
    public static int startStrSub(String haystack, String needle) {
        //判断两个字符串的有效性
        if (haystack.isEmpty() || needle.isEmpty() || haystack.length() < needle.length()) {
            return -1;
        }
        //循环遍历 确保在检查的过程中不会超出原始字符串的范围。
        for (int i = 0; i <= haystack.length() - needle.length(); i++) {
            // 使用 substring 方法获取从当前位置开始的子字符串
            // 然后使用 equals 方法检查这个子字符串是否与指定的子字符串相匹配
            if (haystack.substring(i, i + needle.length()).equals(needle)) {
                //匹配成功返回的下标
                return i;
            }
        }
        return -1;
    }

四、KMP算法

• 思路：就是用过使用KMP算法，构建一个next数组在用字符串匹配的过程中加快速度

    /**
     *
     * @param haystack 原始字符串
     * @param needle   要匹配的子字符串
     * @return 如果找到匹配项，返回匹配项的起始下标；否则返回 -1
     */
    public static int strStrKmp(String haystack, String needle) {
        // 如果needle和haystack有一个是空的 那么肯定不是匹配项
        if (needle.isEmpty() || haystack.isEmpty()) {
            return -1;
        }
        // 构建 next 数组，用于加速匹配过程
        int[] next = getNext(needle);
        int i = 0, j = 0;
        //使用循环 将haystack 和 needle 之间进行匹配
        while (i < haystack.length()) {
            if (haystack.charAt(i) == needle.charAt(i)) {
                //如果当前字符匹配 则匹配下一个
                i++;
                j++;
                //如果j==needle的长度，就表示找到了匹配项 返回匹配的结果
                if (j == needle.length()) {
                    return i - j;
                }
            } else {
                //如果不匹配的情况下 就需要根据next数组进行调配指针
                j = next[j];
                if (j == -1) {
                    //如果j==-1的时候，就表示没有更短的前后缀了，就把i移动到下一个为止
                    i++;
                    j = 0;
                }
            }
        }
        return -1;
    }

    /**
     * 构建 KMP 算法中的 next 数组。
     *
     * @param needle 要匹配的子字符串
     * @return next 数组
     */
    private static int[] getNext(String needle) {
        //初始化数组
        int[] next = new int[needle.length()];
        next[0] = -1;
        int startIndex = 0;
        int endIndex = -1;
        //构建next数组
        while (startIndex <= next.length - 1) {
            if (endIndex == -1 || needle.charAt(startIndex) == needle.charAt(endIndex)) {
                // 如果 endIndex 为 -1（表示当前字符为 needle 的第一个字符）或当前字符匹配
                // 则递增 endIndex 和 startIndex，并更新 next 数组的值
                endIndex++;
                startIndex++;
            } else {
                //如果字符不匹配，则根据next进行调整startIndex
                startIndex = next[startIndex];
            }

        }
        return next;
    }