算法练习03

一、题目

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

• 示例 1:输入:haystack="sadbutsad",needle ="sad"。输出:@

解释:"sad”在下标 0和6 处匹配。第一个匹配项的下标是0，所以返回0

• 示例 2:输入:haystack="leetcode",needle ="leeto"。输出:-1

解释:"leeto"没有在“leetcode”中出现，所以返回-1

二、实现思路

1. 从 haystack 的第一个字符开始，逐个检查从该字符开始的子字符串是否与 needle 相等。

2. 如果找到了匹配的子字符串，则返回该子字符串的起始下标。

3. 如果遍历完整个 haystack 仍未找到匹配的子字符串，则返回 -1。

三、代码实现

package com.thor.test;


public class Demo {
    public static void main(String[] args) {
        //创建一个Solution
        Solution solution = new Solution();
        //示例 1: 输入:haystack="sadbutsad",needle ="sad" 输出:@ 解释:"sad”在下标 0和6 处匹配。 第一个匹配项的下标是0，所以返回0
        String haystack="sadbutsad";
        String needle="sad";
        int result = solution.strStr(haystack, needle);
        System.out.println(result);//0
        //示例 2: 输入:haystack="leetcode",needle ="leeto" 输出:-1 解释:"leeto”不存在于“leetcode”中，所以返回-1
        haystack="leetcode";
        needle="leeto";
        result = solution.strStr(haystack, needle);
        System.out.println(result);//-1

    }
}
class Solution {
    /**
     * @description:
     * @author: Allen
     * @date: 2025/1/9 15:15
     * @param: [haystack, needle]
     * @return:
     **/
    public int strStr(String haystack, String needle){
        //获取haystack的长度和needle的长度
        int n=haystack.length();
        int m=needle.length();
        //如果needle为空，则返回0
        if(m==0){
            return 0;
        }
        //遍历hatstack，检查从每个位置开始的字字符串是否与needle匹配
        for(int i=0;i<=n-m;i++){
            //假设从位置i开始匹配
            int j=0;
            //检查needle的每个字符是否与haystack中对应位置的字符匹配
            while(j<m&&haystack.charAt(i+j)==needle.charAt(j)){
                j++;
            }
            //如果j达到了needle的长度，则说明匹配成功，返回i
            if(j==m){
                return i;
            }
        }
        return -1;
    }
}