Accepted DP-based solution


  • 0
    B

    Here is my accepted DP-based solution. Main idea is for each substring str[i ... j], the ending char str[j] can only fall into two cases:

    1. it does not belong to any repeating pattern, i.e., not str[j] is not inside bracket "[]"
    2. it belongs to some repeating pattern, i.e., str[j] is inside some bracket "[]"
      As for case 2, I used List Array revIdx to store all the positions that certain char appears.

    Any comment or feedback is welcome :)

    Here is my code:

    public class Solution {
        public String encode(String s) {
            // dp[i][j] = min (dp[i][j - 1] + 1, dp[i][m] + numOfDigits(k) + 2 + dp[m + 1][m + l])
            //                              |-> str[j] is not inside "[]",   |-> str[j] is encoded, i.e. insides "[]"
            /*
            i ... m     m + 1 ... m + l     m + l + 1 ... m + 2l    ... ... ... m + (k - 1) * l + 1 ... m + k * l
                        |<-    l       ->|<-           l        ->| ...      |<-                     l           ->|
                        |<-                             k           times                                        ->|
            here, m + k * l == j, s.substring(m + 1, m + l + 1) == ... == s.substring(m + (k - 1) * l + 1, m + k * l + 1)
           
            Notice that k may NOT be the maximum repeated times
            e.g. : "abcdefabcdefffffffffffffedcbafedcba"
    
            also, k * l > numOfDigits(k) + 2 + l
            */
            int len = s.length();
            int[][] dp = new int[len + 1][len + 1]; // dp[i][j] = min encoded len for str[i ... j]
            int[][][] bt = new int[len + 1][len + 1][2]; // bt[i][j][0] = len of repeated unit
                                                         // bt[i][j][1] = repeated times of unit
            List<Integer>[] revIdx = new List[26];
            for (int i = 0; i < 26; i++) {
                revIdx[i] = new ArrayList();
            }
            for (int i = 0; i < len; i++) {
                revIdx[s.charAt(i) - 'a'].add(i);
            }
            helper(s, 0, len - 1, revIdx, dp, bt);
            StringBuilder sb = new StringBuilder();
            genEncode(s, 0, len - 1, sb, dp, bt);
            return sb.reverse().toString();
        }
        public void genEncode(String s, int start, int end, StringBuilder sb, int[][] dp, int[][][] bt) {
            if (start > end) return;
            if (bt[start][end][1] == 1) {
                sb.append(s.charAt(end));
                genEncode(s, start, end - 1, sb, dp, bt);
            } else {
                sb.append("]");
                genEncode(s, end - bt[start][end][0] + 1, end, sb, dp, bt);
                sb.append("[");
                sb.append((new StringBuilder().append(bt[start][end][1])).reverse());
                genEncode(s, start, end - bt[start][end][0] * bt[start][end][1], sb, dp, bt);
            }
        }
        public int helper(String s, int start, int end, List<Integer>[] revIdx, int[][] dp, int[][][] bt) {
            if (start > end) return 0;
            if (dp[start][end] == 0) {
                char endChar = s.charAt(end);
                List<Integer> list = revIdx[endChar - 'a'];
                int currIdx = Collections.binarySearch(list, end);
                int minEncLen = helper(s, start, end - 1, revIdx, dp, bt) + 1; // ending char is not in any repeated pattern
                int minEncUnitLen = 1;
                int minEncTimes = 1;
                for (int i = currIdx - 1; i >= 0; i--) { // repeat pattern str[list.get(i) ... end]
                    int prev = list.get(i);
                    if (prev * 2 < start + end - 1) {break;} // early termination
                                                             // end - list.get(i) <= list.get(i) - start + 1
                    String pattern = s.substring(prev + 1, end + 1);
                    int len = end - prev;
                    while (prev - len + 1 >= start && s.substring(prev - len + 1, prev + 1).equals(pattern)) {
                        prev -= len;
                    }
                    int k = (end - prev) / len; // max number of repeating unit 
                    for (int t = 2; t <= k; t++) { // group all k units together may not be optimal
                                                   // e.g. "abcdefabcdefffffffffffffedcbafedcba"
                        int candEncLen = helper(s, start, end - len * t, revIdx, dp, bt) + getNumOfDigit(t) + 2 + helper(s, end - len + 1, end, revIdx, dp, bt);
                        if (candEncLen < minEncLen) {
                            minEncLen = candEncLen;
                            minEncUnitLen = len;
                            minEncTimes = t;
                        }
                    }
                }
                dp[start][end]= minEncLen;
                bt[start][end][0] = minEncUnitLen;
                bt[start][end][1] = minEncTimes;
                //System.out.println("dp[" + start + "][" + end + "] = " + minEncLen);
                //System.out.println("bt[" + start + "][" + end + "][0] = " + minEncUnitLen);
                //System.out.println("bt[" + start + "][" + end + "][1] = " + minEncTimes);
            }
            return dp[start][end];
        }
        public int getNumOfDigit(int num) { // assume num > 0
            int ret = 0;
            while (num > 0) {
                ret++;
                num /= 10;
            }
            return ret;
        }
    }
    

Log in to reply
 

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