Leetcode 471 Solution

This article provides solution to leetcode question 471 (encode-string-with-shortest-length)
Categories:
Tags:
Access this page by simply typing in "lcs 471" in your browser address bar if you have bunnylol configured.

https://leetcode.com/problems/encode-string-with-shortest-length

Solution

class Solution {
public:
    string encode(string s) {
        int n = s.size();
        if (n == 0)
            return "";

        vector<vector<string>> dp(n, vector<string>(n));

        for (int len = 1; len <= n; len++)
        {
            for (int i = 0; i + len - 1 < n; i++)
            {
                int j = i + len - 1;

                dp[i][j] = s.substr(i, len);
                for (int k = i; k < j; k++)
                {
                    if (dp[i][j].size() > dp[i][k].size() + dp[k + 1][j].size())
                        dp[i][j] = dp[i][k] + dp[k + 1][j];
                }

                string t = s.substr(i, len);
                int pos = (t + t).find(t, 1);
                if (pos != t.size())
                    t = to_string(t.size() / pos) + "[" + dp[i][i + pos - 1] + "]";
                if (t.size() < dp[i][j].size())
                    dp[i][j] = t;
            }
        }

        return dp[0][n - 1];
    }
};