首页 > 代码库 > Leetcode: Implement strStr()
Leetcode: Implement strStr()
Implement strStr().Returns a pointer to the first occurrence of needle in haystack, or null if needle is not part of haystack.
难度：60. 这是算法中比较经典的问题，判断一个字符串是否是另一个字符串的子串。这个题目最经典的算法应该是KMP算法，不熟悉的朋友可以参见Knuth–Morris–Pratt algorithm。KMP算法是最优的线性算法，复杂度已经达到这个问题的下限。但是KMP算法比较复杂，很难在面试的短时间里面完整正确的实现。所以一般在面试中并不要求实现KMP算法。
下面我们先说说brute force的算法，假设原串的长度是n，匹配串的长度是m。思路很简单，就是对原串的每一个长度为m的字串都判断是否跟匹配串一致。总共有n-m+1个子串，所以算法时间复杂度为O((n-m+1)*m)=O(n*m)，空间复杂度是O(1)。代码如下：
1 public class Solution { 2 public String strStr(String haystack, String needle) { 3 if (haystack == null || needle == null) return null; 4 if (needle.length() == 0) return haystack; 5 if (haystack.length() < needle.length()) return null; 6 boolean flag = false; 7 int i = 0; 8 for (; i<=haystack.length()-needle.length(); i++) { 9 String temp = haystack.substring(i, i+needle.length());10 if (temp.equals(needle)) {11 flag = true;12 break;13 }14 }15 if (flag == true) return haystack.substring(i);16 else return null;17 }18 }
网上看到一个线性算法，称为rolling hash，想具体了解的朋友可以参见Rolling hash - Wikipedia。基本思想是用一个hashcode来表示一个字符串，为了保证hash的唯一性，我们用比字符集大的素数为底，以这个素数的幂为基。举例来说，字符集是小写字母集，取素数29为底。比如字符串“abacd",转化为hashcode=1+2*29+1*29^2+3*29^3+4*29^4。然后是如何在前进一步的时候计算新的hashcode，比如匹配串是原串是”abacde“，匹配串长度为5，根据以上的方法计算”abacd“的hashcode=h，那么下一步”bacde“的hashcode=h/29+5*29^4。这是一个constant的操作，所以检测所有子串的时间复杂度只需要O(m+n-m)=O(n)，也是一个线性算法。代码如下
1 public String strStr(String haystack, String needle) { 2 if(haystack==null || needle==null) return null; 3 if(haystack.length()==0){ 4 return needle.length()==0?"":null; 5 } 6 if(needle.length()==0) return haystack; 7 if(haystack.length()<needle.length()) return null; 8 9 int base = 29;10 long patternHash = 0;11 long tempBase = 1;12 13 for(int i=needle.length()-1; i>=0; i--){14 patternHash += (int)needle.charAt(i)*tempBase;15 tempBase *= base;16 }17 18 long hayHash = 0;19 tempBase = 1;20 for(int i=needle.length()-1; i>=0; i--){21 hayHash += (int)haystack.charAt(i)*tempBase;22 tempBase *= base;23 }24 tempBase /= base;25 26 if(hayHash == patternHash){27 return haystack;28 }29 30 for(int i=needle.length(); i<haystack.length(); i++){31 hayHash = (hayHash - (int)haystack.charAt(i-needle.length())*tempBase)*base+(int)haystack.charAt(i);32 if(hayHash == patternHash){33 return haystack.substring(i-needle.length()+1);34 }35 }36 return null;37 }
Leetcode: Implement strStr()
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。