C++ DP readable, Inspired by @70664914


  • 0

    key point:
    dp[i][l] = min_len( repeated_substring, dp[i][k] + dp[k + i][l - k] );
    Inspired by @70664914 from link

    class Solution {
    public:
        
        void helper(vector<vector<string>>& dp, int i, int l, string s) {
            dp[i][l] = s.substr(i, l); // init value
            for (int len = 1; len <= l / 2; len++) { // len denote length of substr
                if (l % len == 0) {
                    bool f = true;
                    for (int k = 1; k < l / len; k++) { // check 
                        if (s.substr(i, len) != s.substr(i + k * len, len)) {
                            f = false;
                            break;
                        }
                    }
                    if (f) {
                        if (dp[i][len].empty())
                            helper(dp, i, len, s);
                        for (int k = 1; k < l / len; k++) {
                            dp[i + k * len][len] = dp[i][len];
                        }
                        if (dp[i][l].size() > to_string(l / len).size() + dp[i][len].size() + 2) {
                            dp[i][l] = to_string(l / len) + '[' + dp[i][len] + ']';
                        }
                    }
                }
            }
            for (int k = 1; k < l; k++) { // divide s into two substr
                if (dp[i][k].empty())
                    helper(dp, i, k, s);
                if (dp[i + k][l - k].empty())
                    helper(dp, i + k,l - k,s);
                if (dp[i][l].size() > dp[i][k].size() + dp[i + k][l - k].size()) {
                    dp[i][l] = dp[i][k] + dp[i + k][l - k];
                }
            }
        }
        string encode(string s) {
            int n = s.size();
            vector<vector<string>> dp(n, vector<string>(n + 1, ""));
            helper(dp, 0, n, s);
            return dp[0][n];
        }
    };
    

Log in to reply
 

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