admin管理员组文章数量:1636943
【原来在SAE的blog上,都转到CSDN了。。】
28. Implement strStr()-leetcode-java
发表于 2016/02/06题意
Implement strStr().
Returns the index of the first occurrence of needle in haystack, or -1 if needle is not part of haystack.
字符串匹配问题,如果子串在主串中存在,则返回子串在主串中首次出现的第一个字符的位置,不存在则返回-1。
思路:遍历主串的长度,如果此时i的位置加上子串长度已经超过主串的长度,说明不存在,返回-1. 在子串开始匹配的时候,为了保留匹配成功时i作为首位字符的位置,用m进行递增。比较子串和主串每一位是否相同,当j等于子串的长度减一,证明匹配成功。
public class Solution {
public int strStr(String haystack, String needle) {
if(haystack==null || needle==null) return 0;
if(needle.length()==0) return 0;
for(int i=0;i<haystack.length();i++){
if(i+needle.length()>haystack.length()) return -1;
int m=i;
for(int j=0;j<needle.length();j++){
if(needle.charAt(j)==haystack.charAt(m)){
if(j==needle.length()-1)
{return i;}
m++;
}else break;
}
}
return -1;
}}
下面这个方法流传也很广,也易于理解:
public int strStr(String haystack, String needle) {
// 从heystack开始
for (int i = 0; ; i++) {
// 匹配needle的字符
for (int j = 0; ; j++) {
// 如果needle和j一样长,则直接返回i(当前匹配的起始位置),因为已经匹配成功了
if (j == needle.length()) { return i; }
// 如果i+j为当前haystack的长度,则表明已经走完heystack所有的字符,并且没有匹配成功(注意如果最后一个字符正好匹配成功,则在上面一个判断就会返回)
if (i + j == haystack.length()) { return -1; }
// 如果当前needle和haystack的字符相同的话(因为每次不成功匹配不成功,则i移动1位,而j又重新从0开始,所以haystack的当前位置是i+j)
if (needle.charAt(j) != haystack.charAt(i + j)) { break; } } } }
此题还有KMP解法,oh这个大boss,光理解它的思想我就已经用完今天的脑力了……
上高手写出来的KMP解法:
public int strStr(String haystack, String needle) { if(haystack==null || needle==null) return 0; int h = haystack.length(); int n = needle.length(); if (n > h) return -1; if (n == 0) return 0; int[] next = getNext(needle); int i = 0; while (i <= h - n) { int success = 1; for (int j = 0; j < n; j++) { if (needle.charAt(0) != haystack.charAt(i)) { success = 0; i++; break; } else if (needle.charAt(j) != haystack.charAt(i + j)) { success = 0; i = i + j - next[j - 1]; break; } } if (success == 1) return i; } return -1; } //calculate KMP array public int[] getNext(String needle) { int[] next = new int[needle.length()]; next[0] = 0; for (int i = 1; i < needle.length(); i++) { int index = next[i - 1]; while (index > 0 && needle.charAt(index) != needle.charAt(i)) { index = next[index - 1]; } if (needle.charAt(index) == needle.charAt(i)) { next[i] = next[i - 1] + 1; } else { next[i] = 0; } } return next; }
在花了些功夫理解思想后,关于next数组的理解把我卡在了半路,又是各种搜,搜到pku的一个ACM PPT把我点通了,和之前博文的讲解串联了起来:
就是下面这个,举的例子来说明运行过程,• i = 1 2 3 4 5 6 7 8 9 …… • A = a b a b a b a a b a b … • B = a b a b a c b • j = 1 2 3 4 5 6 7 •当i=6,j=5时,a[i+1]!=b[j+1],故令j=next[5]=3 • i = 1 2 3 4 5 6 7 8 9 …… • A = a b a b a b a a b a b … • B = a b a b a c b • j = 1 2 3 4 5 6 7 •此时i=6,j=1 仍不满足a[i+1]==b[j+1],故继续减小j,使j=next[1]=0 • i = 1 2 3 4 5 6 7 8 9 …… • A = a b a b a b a a b a b … • B = a b a b a c b • j = 1 2 3 4 5 6 7 •终于,A[8]=B[1],i变为8,j为1 • i = 1 2 3 4 5 6 7 8 9 …… • A = a b a b a b a d b a b … • B = a b a b a c b • j = 1 2 3 4 5 6 7 •事实上,有可能j到了0仍然不能满足A[i+1]=B[j+1](比如A[8]=“d”时)。因此,准确的说法是,当j=0了时,我们直接增加i值但忽略j直到出现A[i]=B[1]为止。 (PS:有一点小小的疑问,上面那里 i 的值是不是写错了,比如最上面那个,i值为7,j=5的时候吧?不过不影响整体的理解)
我认为有助于理解KMP思想的文章:
http://blog.csdn/yutianzuijin/article/details/11954939
这篇文最后作者还给了个科赫曲线,我开始真不理解为啥,懂了之后也就明白了,作者想借此表达一种局部的局部的思想吧,子串也就是pattern串不断向前缩短的同时,也存在着匹配的前缀和后缀。
http://wwwblogs/goagent/archive/2013/05/16/3068442.html
这篇文关于next的公式和图讲的挺好的
http://blog.csdn/power721/article/details/6132380
这篇文用表格的形式描绘了一下匹配过程,也挺直观的。
其他的可以参考学习下的文:
http://www.cppblog/oosky/archive/2006/07/06/9486.html
http://blog.csdn/joylnwang/article/details/6778316
发表在 leetcode
|
标签有 KMP、leetcode、算法
|
发表回复本文标签: implementstrStrJavaLeetCode
版权声明:本文标题:28. Implement strStr()-leetcode-java 内容由热心网友自发贡献,该文观点仅代表作者本人, 转载请联系作者并注明出处:https://www.elefans.com/dongtai/1729233439a1191717.html, 本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如发现本站有涉嫌抄袭侵权/违法违规的内容,一经查实,本站将立刻删除。
发表评论