28. Implement strStr() (Easy)
https://leetcode.com/problems/implement-strstr/
Implement strStr().
Return the index of the first occurrence of needle in haystack, or -1 if needle is not part of haystack.
Example 1:
Input: haystack = "hello", needle = "ll" Output: 2
Example 2:
Input: haystack = "aaaaa", needle = "bba" Output: -1
Clarification:
What should we return when needle
is an empty string? This is a great question to ask during an interview.
For the purpose of this problem, we will return 0 when needle
is an empty string. This is consistent to C's strstr() and Java's indexOf().
Solutions
class Solution {
/*
* This problem is really frustrating with a mass of corn cases.
* Interviewers much take good care of overflow issue. To get rid of overflow,
* It's a good habit to convert all the variables to long type before calculation.
*/
public int divide(int dividend, int divisor) {
// Take care of the overflow issue
if (dividend == Integer.MIN_VALUE && divisor == -1) {
return Integer.MAX_VALUE;
}
if (divisor == 1) {
return dividend;
}
if (divisor == -1) {
return -dividend;
}
boolean isNegative = ((dividend < 0 && divisor > 0) || (dividend > 0 && divisor < 0));
// do not use below statements, Math.abs can be handle int overflow issue
// long tmpDvd = Math.abs(dividend);
// long tmpDvs = Math.abs(divisor);
long tmpDvd = dividend;
long tmpDvs = divisor;
tmpDvd = Math.abs(tmpDvd);
tmpDvs = Math.abs(tmpDvs);
int ans = 0;
long remain = tmpDvd;
while (true) {
if (remain - tmpDvs < 0) {
break;
}
int count = 0;
// 1. comparision must be >= 0, not > 0
// 2. tmpDvs must be long type, or else overflow occurs.
while (remain - (tmpDvs << count) >= 0) {
count++;
}
count--;
// to reach here, count must be >= 0
ans += (1 << count);
// Note that remain - divisor << count is absolutely different from remain - (divisor << count)
remain -= tmpDvs << count;
}
return isNegative ? -ans : ans;
}
}
2.
class Solution {
// The problem should be resolved by KMP algorithm which is the most primitive way to compare strings
// against pattern.
public int strStr(String haystack, String needle) {
return kmpMatch(haystack, needle);
}
private int kmpMatch(String str, String pattern) {
if (pattern == null || pattern.length() == 0) {
return 0;
}
if (str == null || str.length() == 0) {
return -1;
}
char[] strArr = str.toCharArray();
char[] patternArr = pattern.toCharArray();
int[] next = getNextArray(patternArr);
// Pointer of the given str
int strPtr = 0;
// Pointer of the given pattern
int patternPtr = 0;
while (strPtr < strArr.length && patternPtr < patternArr.length) {
// next[0] = -1, so when patternPtr = -1, pattern differ with str at index 0
// so move both strPtr and patternPtr.
if (patternPtr == -1) {
strPtr++;
// patternPtr becomes 0
patternPtr++;
}
// Given pattern matches the given str at the head with patternPtr chars, which means
// strArr[strPtr-patternPtr:strPtr] == pattern[0:patterPtr], carry on the comparison.
else if (strArr[strPtr] == patternArr[patternPtr]) {
strPtr++;
patternPtr++;
}
// patternPtr != -1 && strArr[strPtr] != patternArr[patternPtr], pattern differ with str at certain position,
// but not the first char. Do not move forward the both pointers. Adjust the patternPtr to start a
// new comparison.
else {
// if pattern differ with str at the first char, patternPtr points to -1
patternPtr = next[patternPtr];
}
}
// all matched
if (patternPtr == patternArr.length) {
return strPtr - patternPtr;
}
return -1;
}
private int[] getNextArray(char[] pattern) {
int[] next = new int[pattern.length];
next[0] = -1;
int matchedCount;
for (int j = 1; j < pattern.length; j++) {
// suppose matchedCount = -1 or pattern[j-1] != pattern[matchedCount], next[j] should have a default value.
next[j] = 0;
// previously matched count
matchedCount = next[j - 1];
while (matchedCount != -1) {
// Standing at index j, if previous char pattern[j-1] matches the (matchedCount)th char, current next[j] increases
// And up till index j-1, next[j] chars matches
// matched chars pattern[0:matchedCount-1]
if (pattern[j - 1] == pattern[matchedCount]) {
next[j] = matchedCount + 1;
break;
}
// If not match, technically, we need to start over from the head, but we can take advantage of the previously
// computed offset information.
// !!! Important !!! You can treat substring pattern[j-matchedCount:] as the string to be matched by 'pattern',
// it will be much easier for you to understand.
// Therefore, set matchedCount to the offset that pattern failed to match substring pattern[j-matchedCount:]
// instead of a fresh start.
// Take following pattern string as example, 9th char is 'd' which differs from 5th char 'f', but we don't
// have to search from 6th char, we can take advantage of next[4]=1, then compare 1th char 'd' with 9th char 'd'.
// [0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10] j
// [s, d, f, s, f, s, d, f, s, d, f] pattern
// [-1,0, 0, 0, 1, 0, 1, 2, 3, 4, 2] next
matchedCount = next[matchedCount];
}
}
return next;
}
}