C++ 9ms recursive solution (incorrect)


  • 0
    H

    To get shortest encoded string, we need find the longest consecutive repeated sub string. Then, encode this this sub string. After encoded, we do encode to the new string again until we can't get shorter result.
    For example: "aaaaaaaaaabbbaaaaabbb"

    aaaaaaaaaabbbaaaaabbb=>aaaaa2[aaaaabbb]
    aaaaa2[aaaaabbb]=>5[a]2[aaaaabbb]
    5[a]2[aaaaabbb]=>5[a]2[5[a]bbb]
    

    Unfortunately that is not true for all tests. For abcdefabcdefffffffffffffedcbafedcba , this algorithm will return abcdefabcde13[f]edcbafedcba, the correct answer is 2[abcdef]11[f]2[fedcba]

    class Solution {
    public:
    	string encode(string s) {
    	    int n = s.size();
    	    if (n < 5) return s;
    	    string sub;
    	    int l = 0;
    	    int r = 0;
    	    for (int i = 0; i < n; i++) {
    	        for (int j = i+1; j <= n; j++) {
    	            string t = s.substr(i, j-i);
    	            int k = j;
    	            int len = j - i;
    	            int count = 1;
    	            while(k < n && s.substr(k, len) == t) {
    	                count++;
    	                k += len;
    	            }
                        // at least appear twice and encoded string is shorter than original
                        // and encode range is larger than current one. 3 is the length of "x[]"
    	            if (count > 1 && len+3 < len*count && k-i > r-l) {
                        sub = t;
                        l = i;
                        r = k;
    	            }
    	        }
    	    }
    	    if (r - l > 0) {
    	        int len = r - l;
    	        int count = len / sub.size();
    	        string res = s.substr(0, l) + to_string(count) + "[" + sub + "]" + s.substr(r, n-r);
                    cout << s << "=>" << res << endl;
    	        return encode(res);
    	    }
    	    return s;
    	}
    };
    

Log in to reply
 

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