首页 > 代码库 > Implement strStr() leetcode java
Implement strStr() leetcode java
题目：
Implement strStr().
Returns a pointer to the first occurrence of needle in haystack, or null if needle is not part of haystack.
题解：
其实我觉得这题。。为啥不给个更明确的解释呢？
是不是如果不知道strStr()是干嘛的就给直接挂了呢。。。
这道题就是让你判断，needle是不是haystack的子串，是的话就返回这个子串。
解题想法是，从haystack的第一个位置，开始逐个判断是不是子串。如果整个子串都匹配了，那么就返回，否则继续往下挪位置。
注意要看haystack剩余的长度跟needle比足不足够多，不够的话也就不用往后比了。
写到这突然想起来这个不就是《数据结构》那本书里面那个例子么，这应该是最naive的解法，之后讲的就是kmp解法，可以往后滑动的那种。。。
了解kmp算法网上应该有很多教程，之前是看严蔚敏老师的视频学习的，老师讲的很细，拿着小纸片当指针一个一个指着给你讲，很清楚。。。对我这种理解能力慢的人就恨受用了。。。
我这个就不是kmp了，就最naive的方法。
代码如下：
1 public String strStr(String haystack, String needle) {
2 if (needle.length() == 0)
3 return haystack;
4
5 for (int i = 0; i < haystack.length(); i++) {
6 if (haystack.length() - i + 1 < needle.length())
7 return null;
8
9 int k = i;
10 int j = 0;
11
12 while (j < needle.length() && k < haystack.length() && needle.charAt(j) == haystack.charAt(k)) {
13 j++;
14 k++;
15 if (j == needle.length())
16 return haystack.substring(i);
17 }
18
19 }
20 return null;
21 }
2 if (needle.length() == 0)
3 return haystack;
4
5 for (int i = 0; i < haystack.length(); i++) {
6 if (haystack.length() - i + 1 < needle.length())
7 return null;
8
9 int k = i;
10 int j = 0;
11
12 while (j < needle.length() && k < haystack.length() && needle.charAt(j) == haystack.charAt(k)) {
13 j++;
14 k++;
15 if (j == needle.length())
16 return haystack.substring(i);
17 }
18
19 }
20 return null;
21 }
Reference:http://www.programcreek.com/2012/12/leetcode-implement-strstr-java/
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。