Smart C++ Solution with hash


  • 1
    S
    class Solution {
    public:
        bool checkInclusion(string s1, string s2) {
            int hash1 = hash(s1);
            int len1 = s1.size(), len2 = s2.size();
            if(len1>len2) return false;
            for(int i=0;i<=len2-len1;i++){
                int hash2 = hash(s2.substr(i,len1));
                if(hash1==hash2) return true;
            }
            return false;
        }
        inline int hash(string s){
            int ret = 1;
            for(char i:s)
                ret *= ((i-'a')*(i-'a') + (i-'a')+41) % INT_MAX;
            return ret;
        }
    };
    

  • 0
    L

    smart solution!


Log in to reply
 

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