Encode String with Shortest Length, C++, DP


  • 0
    class Solution {
    public:
        string helper(vector<vector<string>>& dp, string& s, int start, int cnt) {
            if(!dp[start][cnt].empty()) return dp[start][cnt];
            dp[start][cnt] = s.substr(start,cnt);
            for(int len=1;len<cnt;len++) {
                if(cnt%len!=0) continue;
                bool isWrap = true;
                string patStr = s.substr(start,len);
                int k = cnt/len;
                for(int i=0;i<k;i++) {
                    if(s.substr(start+len*i,len)!=patStr) {
                        isWrap = false;
                        break;
                    }
                }
                if(!isWrap) continue;
                helper(dp,s,start,len);
                for(int i=1;i<k;i++) {
                    helper(dp,s,start+len*i,len)=dp[start][len];
                }
                patStr = to_string(k)+"["+dp[start][len]+"]";
                if(patStr.size()<dp[start][cnt].size()) dp[start][cnt] = patStr;
            }
            
            for (int i = 1; i < cnt; ++i) {
                if(dp[start][i].empty()) dp[start][i] = helper(dp,s, start,i);
                if(dp[start + i][cnt - i].empty()) dp[start + i][cnt - i] = helper(dp, s, start + i,cnt - i);
                
    			if (dp[start][cnt].size() > dp[start][i].size() + dp[start+i][cnt-i].size()) {
    				dp[start][cnt] = dp[start][i] + dp[start+i][cnt-i];
    			}
    		}
            
            return dp[start][cnt];
        }
        string encode(string s) {
            int n = s.size();
            if(n==0) return "";
            string ans;
            vector<vector<string>> dp(n+1,vector<string>(n+1,""));
            return helper(dp,s,0,n);
        }
    };
    

Log in to reply
 

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