C++ O(N^3)-time O(N^2)-space solution using memorized dynamic programming with detail explanations


  • 4

    This solution is inspired by @amaximov and @70664914's threads.

    General ideas:

    We use a 2-dimesion storage dp[first][count] to store the shortest encoded string of s[first ... first+count-1]. Therefore, our ultimate goal is to find dp[0][N], where N is the length of s.

    For any first and count, dp[first][count] must be one of the following two cases:

    • Case 1: dp[first][count] is in the form of k[***]. In this case, dp[first][count] can be generated by repeating a substring.

    • Case 2: dp[first][count] is NOT in the form of k[***]. In this case, dp[first][count] can be generated by concatenating two substrings. Let the length of the two substrings be count1 and count - count1, we have

      dp[first][count] = dp[first][count1] + dp[first+count1][count - count1]

    Due to the analysis of Case 2, in order to calculate our ultimate goal dp[0][N], we may need to use dp[first][count] (0<=first<N, 1<=count<=N-first). When using these values, we use memorized dynamic programming.

    • If dp[first][count] has been not yet calculated before, it equals the default value (i.e. the empty string). In this case, we calculate dp[first][count] accordingly.
    • If dp[first][count] has been calcuated before, it does not equal the default value. In this case, we do not need to calculate dp[first][count].

    Complexity

    Time: O(N^3)
    update each value of dp[first][count] require at most O(N) time.
    There are O(N^2) such values.
    So overall time complexity is O(N^3).

    Space: O(N^2)
    The space of dp[][] is O(N^2).

    Code (C++):

    class Solution {
    
    	string memorizedDynamicProgram(vector<vector<string>> & dp, 
    		const string & s, int first, int count) {
    
    		// If dp[first][count] has been calculated,
    		// we do not need to calculate any more.
    		if (!dp[first][count].empty()) {
    			return dp[first][count];
    		}
    
    		// If dp[first][count] has not been calculated,
    		// we calculate it now.
    
    		// default value: the raw string
    		dp[first][count] = s.substr(first, count);
    
    		// test the repetitive pattern of length atomLength
    		for (int atomLength = 1; atomLength < count; ++atomLength){
    			if (count % atomLength == 0) {
    				for (int repeat = 1; repeat < count / atomLength; ++repeat) {
    					if (s.substr(first, atomLength) != s.substr(first + repeat*atomLength, atomLength)) {
    						goto UPDATE_COMPLETE;
    					}
    				}
    
    				// Now we find the repetitive pattern
    				int k = count / atomLength; // the occurance number of repetitive pattern
    				
    				// Update its components (only dp once to avoid duplication)
    				memorizedDynamicProgram(dp, s, first, atomLength); // update[first][atomLength]
    				
    				for (int repeat = 1; repeat < count / atomLength; ++repeat) {
    					dp[first + repeat * atomLength][atomLength] = dp[first][atomLength];
    				}
    
    				// try to update dp[first][count]
    				if (dp[first][count].size() > to_string(k).size() + 2 + dp[first][atomLength].size()) {
    					dp[first][count] = to_string(k) + "[" + dp[first][atomLength] + "]";
    				}
    
    			UPDATE_COMPLETE:
    				;
    			}
    		}
    
    		// concatenate two strings, whose length are count1 and count-count1 respectively
    		for (int count1 = 1; count1 < count; ++count1) {
    			if (dp[first][count].size() > dp[first][count1].size() + dp[first + count1][count - count1].size()) {
    				dp[first][count] = dp[first][count1] + dp[first + count1][count - count1];
    			}
    		}
    		return dp[first][count];
    	}
    
    public:
    	string encode(string s) {
    		int n = s.size();
    
    		vector<vector<string>> dp(n, vector<string>(n + 1)); 
    				// (first, count) -> optimal string
    
    		memorizedDynamicProgram(dp, s, 0, n);
    		return dp[0][n];
    	}
    };

  • 0
    T

    @zhiqing_xiao Thank you for your solution. However, there are one mistakes in your code and also OJ doesn't like GOTO. I modified your code a little bit and it now accepted by OJ. I am not sure my way is the best and would like to see your opinion.

    class Solution {
    
    	string memorizedDynamicProgram(vector<vector<string>> & dp, const string & s, int first, int count) {
    
    		if (!dp[first][count].empty()) {
    			return dp[first][count];
    		}
    
    		dp[first][count] = s.substr(first, count);
    
    		// atomLength <= count / 2;
    		for (int atomLength = 1; atomLength <= count / 2; ++atomLength){
    			if (count % atomLength == 0) {
    			    // OJ dislikes GOTO; Use flag instead;
    			    bool flag = true;
    				for (int repeat = 1; repeat < count / atomLength; ++repeat) {
    					if (s.substr(first, atomLength) != s.substr(first + repeat*atomLength, atomLength)) {
    						flag = false;
    						break;
    					}
    				}
                    if (flag) {
                        
        				int k = count / atomLength; 
        				
        				memorizedDynamicProgram(dp, s, first, atomLength); 
        				
        				for (int repeat = 1; repeat < count / atomLength; ++repeat) {
        					dp[first + repeat * atomLength][atomLength] = dp[first][atomLength];
        				}
        
        				if (dp[first][count].size() > to_string(k).size() + 2 + dp[first][atomLength].size()) {
        					dp[first][count] = to_string(k) + "[" + dp[first][atomLength] + "]";
        				}
                    }
    			}
    		}
    
    		for (int count1 = 1; count1 < count; ++count1) {
    		    // should be "dp[first][count].size() > memorizedDynamicProgram(dp, s, first, count1).size() + memorizedDynamicProgram(dp, s, first + count1, count - count1).size()" since the two parts may not be calculated yet.
    			if (dp[first][count].size() > memorizedDynamicProgram(dp, s, first, count1).size() + memorizedDynamicProgram(dp, s, first + count1, count - count1).size()) {
    				dp[first][count] = dp[first][count1] + dp[first + count1][count - count1];
    			}
    		}
    		
    		return dp[first][count];
    	}
    
    public:
    	string encode(string s) {
    		int n = s.size();
    
    		vector<vector<string>> dp(n, vector<string>(n + 1));
    
    		memorizedDynamicProgram(dp, s, 0, n);
    		return dp[0][n];
    	}
    };
    

  • 0

    @Tongyun_Wu Thank you very much for your comments.

    Yes, as you pointed out. I made a mistake when concatenate two substrings. I should have dp them first, then try to concatenate them together.

    P.S. This problem is now for subscribers only, so I have no access to this problem currently.


  • 2
    I

    @zhiqing_xiao Doesn't dp[first][count] = xxx; takes O(N) time? So why the time complexity is O(N^3) instead of O(N^4)? And the same question as for space complexity.


Log in to reply
 

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