首页 > 代码库 > [leecode]Implement strStr()
[leecode]Implement strStr()
Implement strStr()
Implement strStr().
Returns a pointer to the first occurrence of needle in haystack, or null if needle is not part of haystack.
实现String.class中的contains()接口。
KMP算法
不了解该算法的，请移步KMP算法小结。这个也属于必须要掌握的算法。
【未通过case】needle == “”
代码如下：
public class Solution { public String strStr(String haystack, String needle) { if(haystack == null || needle == null || haystack.length() < needle.length() || (haystack.length() == needle.length() && !haystack.equals(needle)) ) return null;//needle为空串要特别注意 if(needle.equals("") || haystack.equals(needle)) return haystack; int i = 0, j = 0; int[] next = new int[needle.length()]; setNext(needle,next); while(i < haystack.length()){ if(j == -1 || haystack.charAt(i) == needle.charAt(j)){ i++; j++; }else{ j = next[j]; } if(j == needle.length()) return haystack.substring(i - needle.length()); } return null; } private void setNext(String needle,int[] next){ char[] p = needle.toCharArray(); int length = p.length; int k = -1, j = 0; next[0] = -1; while(j < length - 1){ if(k == -1 || p[k] == p[j]){ next[++j] = ++k; }else{ k = next[k]; } } } }
这道题我整理了整整一天，第一次手动的实现了KMP，并作出KMP算法小结。后天还要再复习一下。
[leecode]Implement strStr()
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。