Leetcode: Implement strStr()
14323 ワード
Implement strStr().
Returns a pointer to the first occurrence of needle in haystack, or null if needle is not part of haystack.難易度:60.これはアルゴリズムで古典的な問題であり,1つの文字列が別の文字列のサブ列であるかどうかを判断する.このテーマの最も古典的なアルゴリズムはKMPアルゴリズムであるべきで、よく知らない友达はKnuth–Morris–Pratt algorithmを参照することができます.KMPアルゴリズムは最良の線形アルゴリズムであり,複雑度はこの問題の下限に達している.しかし、KMPアルゴリズムは複雑で、面接の短時間で完全に正確に実現することは難しい.だから一般的に面接ではKMPアルゴリズムの実現は要求されません.
次にbrute forceのアルゴリズムについて述べ,元の列の長さがnであり,マッチング列の長さがmであると仮定する.構想は簡単で,原列の各長さmの文字列に対してマッチング列と一致するか否かを判断する.全部でn-m+1のサブ列があるので、アルゴリズムの時間複雑度はO(n-m+1)であり、temp.equals(needle)の操作複雑度をO(m)とすると(実際にはO(1)と見なすことができる)、総時間複雑度はO((n-m+1)*m)=O(n*m)、空間複雑度はO(m)である.コードは次のとおりです.
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 } 1 public class Solution {
2 public int strStr(String haystack, String needle) {
3 if (haystack==null || needle==null) return -1;
4 for (int i=0; i<=haystack.length()-needle.length(); i++) {
5 String temp = haystack.substring(i, i+needle.length());
6 if (temp.equals(needle)) {
7 return i;
8 }
9 }
10 return -1;
11 }
12 }しかし、これらのbrute forceメソッドはO(m)のspaceであり、O(1)のspaceを使用するには、次のようにします.
1 public class Solution {
2 public int strStr(String haystack, String needle) {
3 if(haystack==null || needle == null || needle.length()>haystack.length())
4 return -1;
5 for(int i=0;i<=haystack.length()-needle.length();i++)
6 {
7 boolean successFlag = true;
8 for(int j=0;j<needle.length();j++)
9 {
10 if(haystack.charAt(i+j)!=needle.charAt(j))
11 {
12 successFlag = false;
13 break;
14 }
15 }
16 if(successFlag)
17 return i;
18 }
19 return -1;
20 }
21 }ネット上でrolling hashという線形アルゴリズムが見られ、具体的に知りたい人はRolling hash - Wikipediaを参照することができます.基本思想は1つのhashcodeで1つの文字列を表すことであり,hashの一意性を保証するために,文字セットより大きい素数をベースとし,この素数のべき乗をベースとする.例えば、文字セットは小文字セットであり、素数29をベースとする.例えば文字列「abacd」は、hashcode=1+2*29+1*29^2+3*29^3+4*29^4に変換されます.次に、マッチング列が元の列である「abacde」、マッチング列の長さが5であるなど、前のステップで新しいhashcodeを計算する方法です.以上の方法で「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 }