6 ms C++ Beats 100% - DP using KMP's Next array.


  • 0
    F

    This is still a O(n^3) Time and O(n^2) Space DP.
    I didn't see any other's solution before I passed this one.
    After my submission, I realized this one is by far the fastest, 2x faster than the 2nd place.
    After comparing with other one's solution, I found two major difference that explains why mine is way faster (You don't care about the common part anyway, right? So I will save some time for you)

    1. Use KMP's Next array to quickly identify the longest repetition of an array;
    2. Store the shortest length parent's index instead of the string itself. So you only need to build the string out after you know which is the shortest string to build.

    Here I won't even try to explain how KMP's Next array works here (as you know, it easily takes 2 pages...)
    Just let me know if you have any questions.

    class Solution {
        vector<vector<int>> dp, nexts, parents;
        void calc_next(const string &pattern, int start_pos)
        {
            nexts[start_pos][start_pos] = start_pos - 1;
            for(int i = start_pos, j = start_pos - 1; i < (int)pattern.size() && j < (int)pattern.size();)
                if (j == start_pos - 1 || pattern[i] == pattern[j])
                    nexts[start_pos][++ i] = ++ j;
                else
                    j = nexts[start_pos][j];
        }
        void calc_rep(const string &str, int start, int end)//end 1-past the end pointer
        {
            int k = nexts[start][end] - start;
            int len = end - start, rep = len / (len - k) ;
            if (len % (len - k) == 0 && rep > 1)
            {
                dp[end - start][start] = to_string(rep).size() + dp[len - k][start] + 2;
                parents[end - start][start] = len - k + str.size();//+ str.size() to indicate this has only 1 parent;
                return;
            }
            parents[end - start][start] = 0;
            dp[end - start][start] = len;
        }
        string build_str(const string &str, int k, int i)
        {
            int j = parents[k][i];
            if (j == 0)
                return str.substr(i, k);
            if (j <= str.size())
                return build_str(str, j, i) + build_str(str, k - j, i + j);
            j -=  str.size(); //j > str.size() means it has only 1 parent instead of 2;
            return to_string(k / j) + "[" + build_str(str, j, i) + "]";
        }
    public:
        string encode(const string &str) {
            nexts.resize(str.size(), vector<int> (str.size() + 1));
            dp.resize (str.size() + 1, vector<int>(str.size()));
            parents.resize(str.size() + 1, vector<int>(str.size()));
            for (int i = 0; i < str.size(); ++i)
                calc_next(str, i);
            for (int k = 1; k <= str.size(); ++k)
                for (int i = 0; i <= str.size() - k; ++ i)
                    for (int j = 0; j < k; ++ j)
                        if (j == 0)
                            calc_rep(str, i, i + k);
                        else if (dp[k][i] >  dp[j][i] + dp[k - j][i + j])
                        {
                            dp[k][i] = dp[j][i] + dp[k - j][i + j];
                            parents[k][i] = j;
                        }
            return build_str(str, str.size(), 0);
        }
    };
    

Log in to reply
 

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