【d35】【Java】【力扣】28. 找出字符串中第一个匹配项的下标

题目

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

提示：

1 <= haystack.length, needle.length <= 104
haystack 和 needle 仅由小写英文字符组成

思路

首先关于不同情况的分类：

1.haystack.length=needle.length：

为了能够进入循环,

分为haystack.length=needle.length>2

和haystack.length=needle.length=1

2.haystack.length>needle.length:（这种情况两个length都大于2）

3.haystack.length<needle.length(感觉没有这种情况，暂时不考虑，以后改进)

综合上面3个情况，能够返回值不是-1 的情况有：

haystack.length=needle.length：

以及以下两种，这两种需要进入循环

haystack.length=needle.length>2

haystack.length>needle.length

具体思路：

定义nf=needle的第一个字符

遍历haystack中的每一个字符，

如果遇到等于nf的字符，则从这里开始判断是否有一个子串等于needle

如果有，返回i，如果没有，返回-1

遇到等于nf的字符时，判断是否有一个子串等于needle，具体判断方法：

在前面定义boolean ifEqualsNeedle = false，表示是否有等于needle的子串

使用双指针，j指向haystack中的元素，k指向needle中的元素，

j和k的最大值判断: j 从 i+1 开始,k从 1 开始，循环次数都是needle.length-1，

于是得到,j最大到<=i+needle.length()-1 ,

k最大到<neesle.length()

//双指针
                    //j表示haystack的下标,最小=i+1,最大到<=i+needle.length()-1
                    //k表示needle的下标，最小=1，最大到<=neesle.length()-1
                    int j = i + 1;
                    int k = 1;
                    while (k<needle.length()) {
                        if (haystack.charAt(j) != needle.charAt(k))
                            break;
                        j++;
                        k++;
                    }
                    if(k==needle.length())
                        ifEqualsNeedle=true;
                    else ;

代码

public class Main {
    public static void main(String[] args) {
        System.out.println(strStr("mississippi", "issip"));
    }

    public static int strStr(String haystack, String needle) {
        int result = -1;
        //needle的第一个字符
        char nf = needle.charAt(0);
        //遍历haystack，当某一个字符=nf时候，看后续是否都匹配
        //遍历的终点 haystack.length()-needle.length()，
        // 因为这之后即使有“某一个字符=nf”，也不可能有等于needle的子串
        boolean ifEqualsNeedle = false;
        if (haystack.equals(needle)) {
            result = 0;
        } else {
            for (int i = 0; i <=haystack.length() - needle.length(); i++) {
                if (haystack.charAt(i) == nf) {
                    //双指针
                    //j表示haystack的下标,最小=i+1,最大到<=i+needle.length()
                    //k表示needle的下标，最小=1，最大到<neesle.length()
                    int j = i + 1;
                    int k = 1;
                    while (k<needle.length()) {
                        if (haystack.charAt(j) != needle.charAt(k))
                            break;
                        j++;
                        k++;
                    }
                    if(k==needle.length())
                        ifEqualsNeedle=true;
                    else ;
                    if (ifEqualsNeedle == true) {
                        result = i;
                        break;
                    } else continue;
                } else ;
            }
        }
        return result;
    }
}