# C++ O(N^3)-time O(N^2)-space solution using memorized dynamic programming with detail explanations

• This solution is inspired by @amaximov and @70664914's threads.

General ideas:

We use a 2-dimesion storage `dp[first][count]` to store the shortest encoded string of `s[first ... first+count-1]`. Therefore, our ultimate goal is to find `dp[0][N]`, where `N` is the length of `s`.

For any `first` and `count`, `dp[first][count]` must be one of the following two cases:

• Case 1: `dp[first][count]` is in the form of `k[***]`. In this case, `dp[first][count]` can be generated by repeating a substring.

• Case 2: `dp[first][count]` is NOT in the form of `k[***]`. In this case, `dp[first][count]` can be generated by concatenating two substrings. Let the length of the two substrings be `count1` and `count - count1`, we have

dp[first][count] = dp[first][count1] + dp[first+count1][count - count1]

Due to the analysis of Case 2, in order to calculate our ultimate goal `dp[0][N]`, we may need to use `dp[first][count]` (`0<=first<N`, `1<=count<=N-first`). When using these values, we use memorized dynamic programming.

• If `dp[first][count]` has been not yet calculated before, it equals the default value (i.e. the empty string). In this case, we calculate `dp[first][count]` accordingly.
• If `dp[first][count]` has been calcuated before, it does not equal the default value. In this case, we do not need to calculate `dp[first][count]`.

Complexity

Time: O(N^3)
update each value of `dp[first][count]` require at most O(N) time.
There are O(N^2) such values.
So overall time complexity is O(N^3).

Space: O(N^2)
The space of `dp[][]` is O(N^2).

Code (C++):

``````class Solution {

string memorizedDynamicProgram(vector<vector<string>> & dp,
const string & s, int first, int count) {

// If dp[first][count] has been calculated,
// we do not need to calculate any more.
if (!dp[first][count].empty()) {
return dp[first][count];
}

// If dp[first][count] has not been calculated,
// we calculate it now.

// default value: the raw string
dp[first][count] = s.substr(first, count);

// test the repetitive pattern of length atomLength
for (int atomLength = 1; atomLength < count; ++atomLength){
if (count % atomLength == 0) {
for (int repeat = 1; repeat < count / atomLength; ++repeat) {
if (s.substr(first, atomLength) != s.substr(first + repeat*atomLength, atomLength)) {
goto UPDATE_COMPLETE;
}
}

// Now we find the repetitive pattern
int k = count / atomLength; // the occurance number of repetitive pattern

// Update its components (only dp once to avoid duplication)
memorizedDynamicProgram(dp, s, first, atomLength); // update[first][atomLength]

for (int repeat = 1; repeat < count / atomLength; ++repeat) {
dp[first + repeat * atomLength][atomLength] = dp[first][atomLength];
}

// try to update dp[first][count]
if (dp[first][count].size() > to_string(k).size() + 2 + dp[first][atomLength].size()) {
dp[first][count] = to_string(k) + "[" + dp[first][atomLength] + "]";
}

UPDATE_COMPLETE:
;
}
}

// concatenate two strings, whose length are count1 and count-count1 respectively
for (int count1 = 1; count1 < count; ++count1) {
if (dp[first][count].size() > dp[first][count1].size() + dp[first + count1][count - count1].size()) {
dp[first][count] = dp[first][count1] + dp[first + count1][count - count1];
}
}
return dp[first][count];
}

public:
string encode(string s) {
int n = s.size();

vector<vector<string>> dp(n, vector<string>(n + 1));
// (first, count) -> optimal string

memorizedDynamicProgram(dp, s, 0, n);
return dp[0][n];
}
};``````

• @zhiqing_xiao Thank you for your solution. However, there are one mistakes in your code and also OJ doesn't like GOTO. I modified your code a little bit and it now accepted by OJ. I am not sure my way is the best and would like to see your opinion.

``````class Solution {

string memorizedDynamicProgram(vector<vector<string>> & dp, const string & s, int first, int count) {

if (!dp[first][count].empty()) {
return dp[first][count];
}

dp[first][count] = s.substr(first, count);

// atomLength <= count / 2;
for (int atomLength = 1; atomLength <= count / 2; ++atomLength){
if (count % atomLength == 0) {
// OJ dislikes GOTO; Use flag instead;
bool flag = true;
for (int repeat = 1; repeat < count / atomLength; ++repeat) {
if (s.substr(first, atomLength) != s.substr(first + repeat*atomLength, atomLength)) {
flag = false;
break;
}
}
if (flag) {

int k = count / atomLength;

memorizedDynamicProgram(dp, s, first, atomLength);

for (int repeat = 1; repeat < count / atomLength; ++repeat) {
dp[first + repeat * atomLength][atomLength] = dp[first][atomLength];
}

if (dp[first][count].size() > to_string(k).size() + 2 + dp[first][atomLength].size()) {
dp[first][count] = to_string(k) + "[" + dp[first][atomLength] + "]";
}
}
}
}

for (int count1 = 1; count1 < count; ++count1) {
// should be "dp[first][count].size() > memorizedDynamicProgram(dp, s, first, count1).size() + memorizedDynamicProgram(dp, s, first + count1, count - count1).size()" since the two parts may not be calculated yet.
if (dp[first][count].size() > memorizedDynamicProgram(dp, s, first, count1).size() + memorizedDynamicProgram(dp, s, first + count1, count - count1).size()) {
dp[first][count] = dp[first][count1] + dp[first + count1][count - count1];
}
}

return dp[first][count];
}

public:
string encode(string s) {
int n = s.size();

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

memorizedDynamicProgram(dp, s, 0, n);
return dp[0][n];
}
};
``````