Use greedy to find repeated pattern and Use DP to find shortest encoding string, beat 99% C++


  • 0
    H

    The idea for the solution is use greedy algorithm to search for repeated sub string, get as many as we can. And use two-dimension dynamic programming to look for shortest encoded string, which is to say if we found a shorter encoding string from any two portion of the current string, let's use it.

    // Use greedy to look for repeated pattern
    void findRepeatPattern(string s, size_t start, size_t end, vector<vector<string>>& result)
    {
        int length = end - start + 1;
        string str = s.substr(start, length);  
        int count = 1;
        size_t next = start + length;
        // use greedy to look for repeated pattern as far as possible
        while ((next + length <= s.size()) && (s.substr(next, length) == str))
        {
            count++;
            // on each repeated substring they should have same encoding
            result[next][next + length - 1] = result[start][end];
            next += length;
            if (count > 1)
            {
                // with each n repeated substring the summary is n[substring]
                if (result[start][next - 1].empty())
                {
                    result[start][next - 1] = s.substr(start, next - start);
                }
                string new_str = to_string(count) + "[" + result[start][end] + "]";
                if (new_str.size() < result[start][next - 1].size())
                {
                    result[start][next - 1] = new_str;
                }
            }
        }
        return;
    }
    
    // Use two dimension programming to look for shortest encoding string
    string encode(string s)
    {
        vector<vector<string>> result(s.size(), vector<string>(s.size()));
        // two dimension programming
        for (size_t step = 0; step < s.size(); step++)
        {
            for (size_t i = 0; i < s.size(); i++)
            {
                if (i + step >= s.size())
                {
                    break;
                }
                // we may process this range before.
                if (result[i][i + step].empty())
                {
                    result[i][i + step] = s.substr(i, step + 1);
                }            
                // less than 5 characters, no need to encode
                if (step >= 4)
                {
                    // search for better option by using sub range
                    for (size_t k = 0; k < step; k++)
                    {
                        // if the whole range can be replaced by the combination of two sub ranges with shorter
                        // encoded string, let's do it.
                        if (result[i][i + step].size() > result[i][i + k].size() + result[i + k + 1][i + step].size())
                        {
                            result[i][i + step] = result[i][i + k] + result[i + k + 1][i + step];
                        }
                    }
    
                }
                findRepeatPattern(s, i, i + step, result);
            }
        }
        return result[0][s.size() - 1];
    }
    
    

Log in to reply
 

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