Two points Java solution. Same O(m+n) but faster than KMP algorithm


  • 0
    L

    73 / 73 test cases passed.
    Status: Accepted
    Runtime: 7 ms

    public int strStr(String haystack, String needle) {
            if( haystack == null || needle== null || needle.length()>haystack.length())
                return -1;
            return indexOf(haystack.toCharArray(), needle.toCharArray());
        }
    
        /**
         * This method refers to JDK String.indexOf() impl.
         */
        public static int indexOf(char[] source, char[] target) {
            if( source == null || target== null || target.length>source.length)
                return -1;
    
            if( target.length ==0 ) return 0;
    
            char first = target[0];
            int max = source.length - target.length;
    
            for (int i = 0; i <= max; i++) {
                /* Look for first character. */
                if (source[i] != first) {
                    while (++i <= max && source[i] != first);
                }
    
                /* Found first character, now look at the rest of v2 */
                if (i <= max) {
                    int j = i + 1;
                    int end = j + target.length - 1; // the end point in source to be matched.
    
                    //match the rest of chars
                    for (int k = 1; j < end && source[j]== target[k]; j++, k++);
    
                    if (j == end) {
                        /* Found whole string. */
                        return i;
                    }
                }
            }
            return -1;
        }
    

Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.