Simple Solution with Hash cpp


  • 0
    C

    The first method came into my mind is O(nm) brute-force, but it's TLE.
    The second method is KMP, but I can't write it quickly and clearly.
    The third method is Hash, which is easy to implement.

    We need a Hash to calculate continuous sequence of chars, and the hash can be updated quickly when removing or adding new char at the head and tail of the string. The simplest one is XOR.

    unsigned int strHash(string str){
        unsigned int res = 0;
        for (int i = 0; i < str.size(); i++)
            res ^= str[i];
        return res;
    }
    
    unsigned int updateHash(char in, char out, unsigned int hashval){
        hashval ^= in;
        hashval ^= out;
        return hashval;
    }
    
    int strStr(string haystack, string needle) {
        if (haystack.size() < needle.size()) return -1;
        int i, j;
        unsigned int tar, val;
        tar = strHash(needle);
        val = strHash(haystack.substr(0, needle.size()));
        i = 0;
        while(true){
            if (tar == val){
                for (j = 0; j < needle.size(); j++)
                    if (haystack[i + j] != needle[j]) break;
                if (j == needle.size()) return i;
            }
            if (i + needle.size() >= haystack.size()) break;
            val = updateHash(haystack[i + needle.size()], haystack[i], val);
            i++;
        }
        return -1;
    }
    

    This hash is too simple to fail in this case:

    aaaaaaaaaaaaaaaaaaaaaaaaaaa...., bbbbbbbbbbbbbbbbb...(even number of 'b')

    Because the hash value will be 0.
    In such case, we can add few checks about matching head or tail or middle.

    Although the hash is very simple, it is enough to pass the test cases here with 6ms.


Log in to reply
 

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