10-line O(N^3) DP solution with comments and detailed explanation


  • 2

    This is my version of the popular DP solution many have posted here. Comments and key observations are added below.

    The shortest encoded string of any string s must be one of the following three cases, whichever is the shortest:

    1. string s itself: "aaa";
    2. repetition of a substring: "ababababab" -> "5[ab]";
    3. concatenation of its two substrings' shortest encoded strings: "aaaaabbbbbb" -> "5[a]6[b]".

    So the DP idea will be straightforward to bottom up calculate each substring's shortest encoded string as well as their repetitive substrings, and compare lengths to get the optimal results.

    Note that shorter substrings' encoded strings must be calculated before longer ones because of case 3.

    I have a post here if you are interested to know the proof behind the implementation of method collapse to calculate the shortest length of a string's repetitive substring.

        string encode(string& s) {
    	dp = vector<vector<string>>(n, vector<string>(1+(n = s.size())));
    	for (L = 1; L <= n; ++L)
              for (i = 0; i + L - 1 < n; ++i) {
        		collapse(dp[i][L] = s.substr(i,L));
        		for (int j = 1; j < L; ++j)
        		  if (dp[i][j].size()+dp[i+j][L-j].size() < dp[i][L].size()) dp[i][L] = dp[i][j]+dp[i+j][L-j];
        	  }
    	return dp[0][n];        
        }
        
        vector<vector<string>> dp; // dp[i][L] = shortest encoded string of s.substr(i,L)
        size_t n, pos, i/*start index*/, L/*sub length*/;
        
        void collapse(string& s) { // collapse s if shorter
    	if ((pos=(s+s).find(s,1)) < L) s = to_string(L/pos)+'['+dp[i][pos]+']';
        }
    

Log in to reply
 

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