LeetCode-028-ImplementstrStr()

ImplementstrStr()题目描述：实现strStr()函数。给你两个字符串haystack和needle，请找到字符串needle在haystack字符串中的第一个位置（下标从0开始）。如果不存在则返回-1。例子见LeetCode官网。来源：LeetCode链接：https://leetcode-cn.com/probl...版权归LeetCode所有。商业转载请联系官方授权，非商业转载请注明出处。解决方案一：穷举法首先，如果needle为空，直接返回0；如果haystack为空或者haystack的长度小于needle的长度，直接返回-1；否则，从haystack的第一位开始与needle匹配，如果没有匹配，则继续遍历haystack，直到遍历完成，即可得到结果。说明：这种方法效率比较差。方案二：KMP算法首先构造一个next数组，先计算出下一个跳转的位置，然后根据next数组的位置遍历匹配原字符串和匹配字符串。importcom.google.common.base.Strings;publicclassLeetCode_028{/***穷举法**@paramhaystack*@paramneedle*@return*/publicstaticintstrStr(Stringhaystack,Stringneedle){if(needle==null||needle.length()==0){return0;}if(haystack==null||haystack.length()==0||haystack.length()0&&needleList[i]!=needleList[j+1]){j=next[j];}//如果匹配成功，先让j++if(needleList[i]==needleList[j+1]){j++;}//更新next[i]，结束这个循环，i++next[i]=j;}//匹配过程，i=1,j=0开始，i小于等于原字符串长度【匹配i从1开始】for(inti=1,j=0;i<=haystackLength;i++){//匹配不成功j=next[j]while(j>0&&haystackList[i]!=needleList[j+1]){j=next[j];}//如果匹配成功，先让j++，然后循环后i++if(haystackList[i]==needleList[j+1]){j++;}//整段匹配成功，直接返回下标if(j==needleLength){returni-needleLength;}}返回-1；}publicstaticvoidmain(String[]args){System.out.println(strStr("mississippi","issi"));System.out.println(strStr2("mississippi","issi"));}}【每日留言】在最美的年华，做最喜欢的事，不辜负美好时光，借时间之手，温暖花开处，借晴空，拥抱梦想