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;
    }
}

Incorrect Solutions

References