C++ DP solution

• #define LENGTH(s) (s.length())

class Solution {
bool check(string &s, int i, int j, int k, int &cnt){
int len= j-i+1;
if (len% (k-i+1)!=0) return false;
string res;
cnt = len/(k-i+1);
string out = s.substr(i-1, k-i+1);
for (int ii=0;ii<cnt;ii++){
res+=out;
}
return res==s.substr(i-1, j-i+1);
}
public:
string encode(string s) {
// dp[i][j]= min(dp[i][k]+dp[k+1][j],..., (i,k,j))
int n = s.length();
vector<vector<string>> dp(n+1, vector<string>(n+1));

``````    int len, i, j,k;

for (i=1;i<=n;i++){
for (j=i;j<=n;j++){
dp[i][j]= s.substr(i-1, j-i+1);
}
}

for (len=2;len<=n;len++){
for (i=1;i<=n-len+1;i++){
j = i+len-1;
for (k=i;k<j;k++){
if (LENGTH(dp[i][j])>LENGTH(dp[i][k])+LENGTH(dp[k+1][j])){
dp[i][j]= dp[i][k]+dp[k+1][j];
}
int cnt;
if (check(s, i, j, k,cnt)){
int nl=LENGTH(dp[i][k])+2;
string val=to_string(cnt);
nl += val.length();
if (LENGTH(dp[i][j])>nl){
dp[i][j]=val+"["+dp[i][k]+"]";
}
}
}
}
}
return dp[1][n];
}
``````

};

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