C++ DP solution

  • 0

    #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++){
    return res==s.substr(i-1, j-i+1);
    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){
        return dp[1][n];


Log in to reply

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