C++ 3 different short clean soliutions: 1 line lib call, 17 lines KMP, and 12 lines brute force


  • 0

    3 ms 1 line lib call:

    int strStr(string haystack, string needle) {       
            return haystack.find(needle);
    }
    

    3 ms 17 lines KMP approach with detailed comments:

    int strStr(string haystack, string needle) {
            // only make sense to search for matching if haystack is longer than needle
            if (haystack.length() <= needle.length()) { return haystack == needle ? 0 : -1; }
            
            // some variables
            /* 
                hi: position in haystack when doing KMP search; ni: position in needle when doing KMP search
                hl: haystack length; nl: needle length
                index[nl]: KMP table for needle
            */ 
            int hi = 0, ni = 0, hl = haystack.length(), nl = needle.length(), index[nl]; index[0] = -1;      
            
            // build KMP table for needle       
            // basically looking for longest matching prefix/suffix using DP
            for (int i = 1; i < nl; i++) {
                int prei = index[i - 1];                // prei: index for possible longest matching prefix
                while (prei >= 0 && needle[prei + 1] != needle[i]) { prei = index[prei]; }
                index[i] = needle[prei + 1] == needle[i] ? prei + 1 : -1;
            }
            
            // KMP search in haystack
            // very similar to above (building KMP table)
            // just that this time it is between haystack's prefix and needle's prefix instead of needle's prefix and suffix
            while (hi < hl && ni < nl) {
                if (haystack[hi] == needle[ni]) { 
                    hi++, ni++;                         // found a matching char so move forward
                } else if (ni == 0) {
                    hi++;                               // update start and hi if no more matching prefix in needle, 
                } else {
                    ni = index[ni - 1] + 1;             // ni move to the next possible matching prefix in needle
                }
            }
            
            return ni == nl ? hi - nl : -1;
    }
    

    3 ms 12 lines brute force approach:

    int strStr(string haystack, string needle) {
            int hL = haystack.length(), nL = needle.length();
            for (int i = 0; i < (hL - nL + 1); i++) {
                bool same = true;
                for (int j = 0; j < nL; j++) {
                    if(haystack[i + j] != needle[j]) {
                        same = false;
                        break;
                    }
                }
                if (same) { return i; }
            }
            
            return -1;
    }
    

Log in to reply
 

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