ftp网站上传成功后怎么做,网站维护 上海,开发网站平台,wordpress图片页面模板下载面试经典150题 day23 题目来源我的题解方法一 库函数方法二 自定义indexOf函数方法三 KMP算法 题目来源
力扣每日一题#xff1b;题序#xff1a;28
我的题解
方法一 库函数 直接使用indexOf函数。 时间复杂度#xff1a;O(n) 空间复杂度#xff1a;O(1) public int str… 面试经典150题 day23 题目来源我的题解方法一 库函数方法二 自定义indexOf函数方法三 KMP算法 题目来源
力扣每日一题题序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 nhaystack.length();for(int i0;in-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 nneedle.length();int i0;while(istarthaystack.length()inhaystack.charAt(istart)needle.charAt(i))i;return in?true:false;
}方法三 KMP算法 KMP算法详情参见宫水三叶 时间复杂度O(nm)。其中 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 mhaystack.length();int nneedle.length();if(needlenull||n0)return 0;int next[]new int[n];char need[]needle.toCharArray();int i1,j0;// 构造next数组while(in){//if(need[i]need[j]){j1;next[i]j;i;}else{if(j0){next[i]0;i;}else{jnext[j-1];}}}i0;j0;char hay[]haystack.toCharArray();while(im){if(hay[i]need[j]){i;j;}else{if(j0){i;}else{jnext[j-1];}}if(jn)return i-j;}return -1;
}有任何问题欢迎评论区交流欢迎评论区提供其它解题思路代码也可以点个赞支持一下作者哈~
