admin管理员组文章数量:1636923
题目:
Implement strStr().
Returns the index of the first occurrence of needle in haystack, or -1 if needle is not part of haystack.
题意:
实现strStr()
返回needle在haystack中第一次出现的位置,如果haystack中不存在needle,返回-1.
算法分析:
方法一:
* in Java, there is an API function name indexof(),
* it returns index within this string of the first occurrence of the specifiedsubstring.
方法二:
* 最native的做法
* 解题想法是,从haystack的第一个位置,开始逐个判断是不是子串。如果整个子串都匹配了,那么就返回,否则继续往下挪位置。
* 注意要看haystack剩余的长度跟needle比足不足够多,不够的话也就不用往后比了。
方法三:
* 利用看毛片(KMP)算法,但是对于一个easy难度的题,利用这么费脑的算法没必要吧~~
* 有兴趣的参考《从头到尾彻底理解KMP》http://blog.csdn/v_july_v/article/details/7041827
* 代码也在下面给出来。
AC代码:
方法一:
//in Java, there is an API function name indexof(),
//it returns index within this string of the first occurrence of the specifiedsubstring.
public class Solution
{
public int strStr(String haystack, String needle)
{
int i;
i=haystack.indexOf(needle);
return i;
}
}
方法二:
/**
* 最native的做法
* 解题想法是,从haystack的第一个位置,开始逐个判断是不是子串。如果整个子串都匹配了,那么就返回,否则继续往下挪位置。
* 注意要看haystack剩余的长度跟needle比足不足够多,不够的话也就不用往后比了。
*/
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) {
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;
}
本文标签: JavaLeetCodestrStrimplement
版权声明:本文标题:[LeetCode][Java] Implement strStr() 内容由热心网友自发贡献,该文观点仅代表作者本人, 转载请联系作者并注明出处:https://m.elefans.com/xitong/1729234916a1191881.html, 本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如发现本站有涉嫌抄袭侵权/违法违规的内容,一经查实,本站将立刻删除。
发表评论