首页 > 代码库 > 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 }

Reference:http://www.programcreek.com/2012/12/leetcode-implement-strstr-java/