Wednesday, September 23, 2020

LeetCode [471] Encode String with Shortest Length

 471. Encode String with Shortest Length

Hard

Given a non-empty string, encode the string such that its encoded length is the shortest.

The encoding rule is: k[encoded_string], where the encoded_string inside the square brackets is being repeated exactly k times.

Note:

  1. k will be a positive integer and encoded string will not be empty or have extra space.
  2. You may assume that the input string contains only lowercase English letters. The string's length is at most 160.
  3. If an encoding process does not make the string shorter, then do not encode it. If there are several solutions, return any of them is fine.

 

Example 1:

Input: "aaa"
Output: "aaa"
Explanation: There is no way to encode it such that it is shorter than the input string, so we do not encode it.

 

Example 2:

Input: "aaaaa"
Output: "5[a]"
Explanation: "5[a]" is shorter than "aaaaa" by 1 character.

 

Example 3:

Input: "aaaaaaaaaa"
Output: "10[a]"
Explanation: "a9[a]" or "9[a]a" are also valid solutions, both of them have the same length = 5, which is the same as "10[a]".

 

Example 4:

Input: "aabcaabcd"
Output: "2[aabc]d"
Explanation: "aabc" occurs twice, so one answer can be "2[aabc]d".

 

Example 5:

Input: "abbbabbbcabbbabbbc"
Output: "2[2[abbb]c]"
Explanation: "abbbabbbc" occurs twice, but "abbbabbbc" can also be encoded to "2[abbb]c", so one answer can be "2[2[abbb]c]".


 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
class Solution {
    class Pair{
        String seg;//minimal repeated segments
        int count;//coount of seg
        String encode;//encoded result
        int len;//length of encode
        Pair(int c, String s){
            count = c;
            seg = s;
            String enc = count+"["+seg+"]";//compute potential encoded string
            String org = "";//if not encoded
            for(int i=0; i<c; ++i) org+=seg;
            encode = enc.length() < org.length() ? enc : org;
            len = encode.length();
        }
    }

    Map<String, String> map = new HashMap<>();
    public String encode(String s) {
        int n = s.length();
        Pair[][] dp = new Pair[n][n];//dp[i][j] records the min-length encoded string for s[i..j]
        for(int i=n-1; i>=0; --i){
            for(int j=i; j<n; ++j){
                String t = s.substring(i, j+1);
                dp[i][j] = new Pair(1, t);
                //cut s[i..j] into s[i..k-1] and s[k..j]
                for(int k=j; k>i; --k){
                    //found a shorted segment for s[i..j] because the min-length encoded string must be composed by the shortest segment
                    if(dp[k][j].seg.equals(dp[i][k-1].seg)){
                        String seg = dp[i][k-1].seg;
                        int cnt = dp[k][j].count + dp[i][k-1].count;
                        if(dp[i][j].seg.length()>seg.length()) dp[i][j] = new Pair(cnt, seg);
                    //found a shorted encoding method
                    }else if(dp[i][k-1].len + dp[k][j].len<dp[i][j].len){
                        String enc = dp[i][k-1].encode+dp[k][j].encode;
                        dp[i][j] = new Pair(1, enc);
                    }
                }
            }
        }
        return dp[0][n-1].encode;
    }


}


condition "(s+s).find(s,1) < s.size()" is equivalent to substring repetition
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
class Solution {
    public String encode(String s) {
        int n = s.length();
        String[][] en = new String[n][n];

        for(int l=1; l<=n; ++l){
            for(int i = 0; i+l-1<n; ++i){
                int j = i+l-1;
                String str = s.substring(i, j+1);
                en[i][j] = str;
                for(int k=i; k<j; ++k){
                    if(en[i][j].length()>en[i][k].length()+en[k+1][j].length()){
                        en[i][j] = en[i][k]+en[k+1][j];
                    }
                }
                int repeatedLen = (str+str).indexOf(str, 1);
                if(repeatedLen>0 && repeatedLen<l){
                    String strsub = en[i][i+repeatedLen-1];
                    String strEncoded = String.valueOf(l/repeatedLen)+"["+strsub+"]";
                    if(strEncoded.length()<en[i][j].length()) en[i][j] = strEncoded;
                }
            }
        }

        return en[0][n-1];
    }
}
at

No comments:

Post a Comment