String Replace - Linkedin
Implement strStr() | N00tc0d3r
The strstr function locates a specified substring within a source string. Strstr returns a pointer to the first occurrence of the substring in the source. If the substring is not found, strstr returns a null pointer.
X. KMP
https://www.programcreek.com/2012/12/leetcode-implement-strstr-java/
http://yyeclipse.blogspot.com/2013/02/leetcode-implement-strstr-string.html
Rolling Hash Algorithm
Here's a simple example of rolling hash.
Input: char array A[1...10]. Length k=5.
H[1..5] = A[1]*a^4 + A[2]*a^3 + A[3]*a^2 + A[4]*a^1 + A[5]*a^0
Then how can we compute H[2..6] ?
Instead of computing it from scratch, we can do as following based on H[1..5]
1. Remove first item of H[1..5] : H[2..6] = H[1..5] - A[1]*a^4
2. Times constant a : H[2..6] *= a
3. Add last item A[6] : H[2..6] += A[6]
public class StrStrRollingHash {
public static final int A = 3;
public String strStr(String haystack, String needle) {
int n = haystack.length();
int m = needle.length();
if(m==0)
return haystack;
if(n<m)
return null;
char[] input = haystack.toCharArray();
int needleHash = getHash(needle.toCharArray(),0,m-1);
int haystackHash = getHash(input,0,m-1);
for(int i=0;i<n-m;i++){
if(haystackHash==needleHash){
if(haystack.substring(i, i+m).equals(needle))
return haystack.substring(i);
}
//rolling hash
haystackHash-=(int)(input[i]*Math.pow(A, m-1));//remove i th item
haystackHash*=A;//times A
haystackHash+=input[i+m];//add i+m th item
}
if(haystackHash==needleHash){
if(haystack.substring(n-m, n).equals(needle))
return haystack.substring(n-m);
}
return null;
}
private static int getHash(char[] array,int start,int end){
int k=end-start;
int sum=0;
for(int i=start;i<=end;i++){
int item = (int)(array[i]*Math.pow(A,k--));
sum+=item;
}
return sum;
}
https://chazyhabit.wordpress.com/2014/07/16/implement-strstr-leetcode-7/
Brute Force:
https://discuss.leetcode.com/topic/18839/elegant-java-solution
http://vivianjiang12.blogspot.com/2012/09/leetcode-implement-strstr.html
public String strStr(String haystack, String needle) {
if(needle.length() == 0) return haystack;
int n = 0;
for(int i = 0; i <= haystack.length() - needle.length(); i++){
n = 0;
while(n < needle.length() && haystack.charAt(i+n) == needle.charAt(n))
n++;
if(n == needle.length()) return haystack.substring(i);
}
return null;
}
X.
https://leetcode.com/problems/implement-strstr/discuss/12807/Elegant-Java-solution
Implement strStr() | N00tc0d3r
The strstr function locates a specified substring within a source string. Strstr returns a pointer to the first occurrence of the substring in the source. If the substring is not found, strstr returns a null pointer.
public String strStr(String haystack, String needle)
X. KMP
https://www.programcreek.com/2012/12/leetcode-implement-strstr-java/
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; }https://eugenejw.github.io/2017/07/leetcode-28
public int strStr(String haystack, String needle) {
int[] kmpTable= new int[needle.length()];
buildKMPTable(needle, kmpTable);
int i = 0;
int j = 0;
int N = haystack.length();
int M = needle.length();
while (i < N && j < M) {
if (haystack.charAt(i) == needle.charAt(j)) {
i++;
if (++j == M) {
return i - j;
}
} else {
if (j == 0) {
i++;
}
else{
j = kmpTable[j-1];
}
}
}
if (M == 0) return 0; // when needle is null
return -1;
}
private void buildKMPTable(String needle, int[] kmpTable) {
int j = 0;
int i = 1;
while (i < kmpTable.length) {
if (needle.charAt(i) == needle.charAt(j)) {
kmpTable[i++] = ++j;
} else {
if (j == 0){
kmpTable[i++] = 0;
} else {
j = kmpTable[j-1];
}
}
}
}http://yyeclipse.blogspot.com/2013/02/leetcode-implement-strstr-string.html
Rolling Hash Algorithm
Here's a simple example of rolling hash.
Input: char array A[1...10]. Length k=5.
H[1..5] = A[1]*a^4 + A[2]*a^3 + A[3]*a^2 + A[4]*a^1 + A[5]*a^0
Then how can we compute H[2..6] ?
Instead of computing it from scratch, we can do as following based on H[1..5]
1. Remove first item of H[1..5] : H[2..6] = H[1..5] - A[1]*a^4
2. Times constant a : H[2..6] *= a
3. Add last item A[6] : H[2..6] += A[6]
public class StrStrRollingHash {
public static final int A = 3;
public String strStr(String haystack, String needle) {
int n = haystack.length();
int m = needle.length();
if(m==0)
return haystack;
if(n<m)
return null;
char[] input = haystack.toCharArray();
int needleHash = getHash(needle.toCharArray(),0,m-1);
int haystackHash = getHash(input,0,m-1);
for(int i=0;i<n-m;i++){
if(haystackHash==needleHash){
if(haystack.substring(i, i+m).equals(needle))
return haystack.substring(i);
}
//rolling hash
haystackHash-=(int)(input[i]*Math.pow(A, m-1));//remove i th item
haystackHash*=A;//times A
haystackHash+=input[i+m];//add i+m th item
}
if(haystackHash==needleHash){
if(haystack.substring(n-m, n).equals(needle))
return haystack.substring(n-m);
}
return null;
}
private static int getHash(char[] array,int start,int end){
int k=end-start;
int sum=0;
for(int i=start;i<=end;i++){
int item = (int)(array[i]*Math.pow(A,k--));
sum+=item;
}
return sum;
}
https://chazyhabit.wordpress.com/2014/07/16/implement-strstr-leetcode-7/
public String strStr(String haystack, String needle) { if(haystack==null || needle==null||haystack.length()<needle.length()) return null; if(needle.length()==0) return haystack; int base = 29; long needleHash = 0; long tempBase = 1; // get the hashcode for the needle for(int i=needle.length()-1; i>=0; i--){ needleHash += (long) needle.charAt(i) * tempBase; tempBase *= base; } long hayHash = 0; tempBase = 1; // get the hashcode for the first substring of haystack for(int i=needle.length()-1; i>=0; i--){ hayHash += (long) haystack.charAt(i) * tempBase; tempBase *= base; } tempBase /= base; // check the first substring if(hayHash == needleHash) return haystack; // traverse the rest substring, get hashcode and check for(int i=needle.length(); i<haystack.length(); i++){ hayHash = (hayHash - (long) haystack.charAt(i-needle.length()) * tempBase) * base + (long) haystack.charAt(i); if(hayHash == needleHash){ return haystack.substring(i-needle.length()+1); } } return null; }Brute Force:
https://discuss.leetcode.com/topic/18839/elegant-java-solution
public int strStr(String s, String t) {
if (t.isEmpty()) return 0; // edge case: "",""=>0 "a",""=>0
for (int i = 0; i <= s.length() - t.length(); i++) {
for (int j = 0; j < t.length() && s.charAt(i + j) == t.charAt(j); j++)
if (j == t.length() - 1) return i;
}
return -1;
} public int strStr(String haystack, String needle) {
int l1 = haystack.length(), l2 = needle.length();
if (l1 < l2) {
return -1;
} else if (l2 == 0) {
return 0;
}
int threshold = l1 - l2;
for (int i = 0; i <= threshold; ++i) {
if (haystack.substring(i,i+l2).equals(needle)) {
return i;
}
}
return -1;
}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 String strStr(String haystack, String needle) {
if(needle.length() == 0) return haystack;
int n = 0;
for(int i = 0; i <= haystack.length() - needle.length(); i++){
n = 0;
while(n < needle.length() && haystack.charAt(i+n) == needle.charAt(n))
n++;
if(n == needle.length()) return haystack.substring(i);
}
return null;
}
X.
https://leetcode.com/problems/implement-strstr/discuss/12807/Elegant-Java-solution
public int strStr(String haystack, String needle) {
for (int i = 0; ; i++) {
for (int j = 0; ; j++) {
if (j == needle.length()) return i;
if (i + j == haystack.length()) return -1;
if (needle.charAt(j) != haystack.charAt(i + j)) break;
}
}
} public int strStr(String haystack, String needle) {
int l1 = haystack.length(), l2 = needle.length();
if (l1 < l2) {
return -1;
} else if (l2 == 0) {
return 0;
}
int threshold = l1 - l2;
for (int i = 0; i <= threshold; ++i) {
if (haystack.substring(i,i+l2).equals(needle)) {
return i;
}
}
return -1;
}
