C++ ,using DP , O(n^3) time complexity


  • 2
    J
    string encode(string s) {
        int n = (int)s.size();  if(!n)  return s;
        // dp[N][i] means length is N, start from i
        vector<vector<string>> DP(n+1,vector<string>(n,""));  
        for(int i = 0; i < n; ++i)  DP[1][i] += s[i];
        for(int N = 2; N <= n; ++N){
            for(int i = 0; i+N <= n; ++i){
                DP[N][i] = s.substr(i,N);
                auto k = ( DP[N][i]+ DP[N][i]).find( DP[N][i],1);
                if(k < DP[N][i].size()){
                    string tmp = to_string(N/k)+"["+DP[k][i]+"]";
                    if(tmp.size() < DP[N][i].size())    DP[N][i] = tmp;
                }
                for(int k=1;k<N;k++)    {
                    string tmp = DP[k][i]+DP[N-k][i+k];
                    if(tmp.size() < DP[N][i].size())    DP[N][i] = tmp;
                }
            }
        }
        return DP[n][0];
    }
    

Log in to reply
 

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