面试经典150题——找出字符串中第一个匹配项的下标

题目来源

力扣每日一题；题序：28

我的题解

方法一 库函数

直接使用indexOf函数。

时间复杂度：O(n)
空间复杂度：O(1)

public int strStr(String haystack, String needle) {return haystack.indexOf(needle);
}

方法二 自定义indexOf函数

每次找到needle开始字符匹配的位置，然后从该位置开始判断是否能够生成needle字符串。

时间复杂度：O(nm)。外层循环遍历了 haystack 字符串的每个字符，内层循环则在 needle 字符串的长度范围内进行比较。因此，时间复杂度为 O(nm)，其中 n 是 haystack 字符串的长度，m 是 needle 字符串的长度。
空间复杂度：O(1)

public int strStr(String haystack, String needle) {int n=haystack.length();for(int i=0;i<=n-needle.length();i++){if(haystack.charAt(i)==needle.charAt(0)&&indexOf(haystack,needle,i)){return i;}}return -1;
}
public boolean indexOf(String haystack,String needle,int start){int n=needle.length();int i=0;while(i+start<haystack.length()&&i<n&&haystack.charAt(i+start)==needle.charAt(i))i++;return i==n?true:false;
}

方法三 KMP算法

KMP算法详情参见：宫水三叶

时间复杂度：O(n+m)。其中 n 是字符串 haystack 的长度，m 是字符串 needle 的长度。至多需要遍历两字符串一次。
空间复杂度：O(m)

public int strStr(String haystack, String needle) {return KMP(haystack,needle);
}
public int KMP(String haystack,String needle){int m=haystack.length();int n=needle.length();if(needle==null||n==0)return 0;int next[]=new int[n];char need[]=needle.toCharArray();int i=1,j=0;// 构造next数组while(i<n){//if(need[i]==need[j]){j+=1;next[i]=j;i++;}else{if(j==0){next[i]=0;i++;}else{j=next[j-1];}}}i=0;j=0;char hay[]=haystack.toCharArray();while(i<m){if(hay[i]==need[j]){i++;j++;}else{if(j==0){i++;}else{j=next[j-1];}}if(j==n)return i-j;}return -1;
}

有任何问题，欢迎评论区交流，欢迎评论区提供其它解题思路（代码），也可以点个赞支持一下作者哈😄~