A Genarally Faster than O(Str1.Length * Str2.Length) Solution


  • 0
    F

    My code's run time is O(kL2logL1), where K is the rounds for s1 and s2' matching pattern to reoccur. For example:
    S1:ababab
    S2:bab
    K = 3: because ababab|ababab contains 3 bab, after 3 repetitions of bab, the matching pattern reoccur.

    So in average case, the code's run time is faster than O(l1*l2) But in a worst case, it can be as worse as O(L1 * L2 * lgL1).
    One example of the worst case is:
    S1:a....a (100 a's)
    S2:a....a(99 a's)
    K = 100: because S2 needs to repeat 100 times before the matching pattern reoccurs.

    class Solution {
        vector<int> charmap [256];
        void buildmap(const string & s1)
        {
            for (int i = 0; i < s1.size(); ++i)
                charmap[s1[i]].push_back(i);
        }
    public:
        int getMaxRepetitions(string s1, int n1, string s2, int n2) {
            buildmap(s1);
            int rep = 0,  last_pos = -1, mult = 0, start_pos = -1, first_start_pos = -2, last_last_pos = -2, last_rep = 0;
            vector<int> reps = {0};
            while (true)
            {
                for (int i = 0; i < s2.size();)
                {
                    auto & v = charmap[s2[i]];
                    if (v.empty())
                        return 0;
                    auto iter = upper_bound(v.begin(), v.end(), last_pos);
                    if (iter == v.end())
                    {
                        rep ++;
                        reps.push_back(mult);
                        last_pos = -1;
                        continue;   
                    }
                    last_pos = *iter;
                    ++ i;
                }
                start_pos = last_pos + 1;
                for (int i = s2.size() - 1; i >= 0;)
                {
                    auto & v = charmap[s2[i]];
                    auto iter = upper_bound(v.rbegin(), v.rend(), start_pos, std::greater<int>());
                    if (iter == v.rend())
                    {
                        start_pos = s1.size();
                        continue;   
                    }
                    start_pos = *iter;
                    -- i;
                }
                mult ++;
                if (start_pos == first_start_pos)
                {
                    mult --;
                    break;
                }
                if (first_start_pos == -2)
                    first_start_pos = start_pos;
                last_last_pos = last_pos;
                last_rep = rep;
            }
            last_rep ++;
            if (first_start_pos <= last_last_pos)
                return ((n1 / last_rep) * mult + reps[n1 % last_rep])/n2;
            return ((n1 - 1) / (last_rep - 1) * mult + reps[(n1 - 1) % (last_rep - 1) + 1])/n2;
        }
    };
    
    

Log in to reply
 

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