C++ DP solution


  • 0
    N

    #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];
    }
    

    };


Log in to reply
 

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