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

2023-12-25 21:23:11

给你两个字符串 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;
    }

文章来源:https://blog.csdn.net/qq_49354230/article/details/135186800
本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。