# 471 Encode String with Shortest Length

給一個非空字串的String，且encoding rule為 k[encoded_string]，回傳encode最終結果。encode完的結果必須比原字串短，且可以有多層括號。

example:

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

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]".

Concept
開一二維陣列，String dp[i][j]表示substring(i,j)的縮寫。
走過所有可能的substring，1. 檢查每個string的長度必須大於四，2.把該string分成兩半，更新dp[i][j] = min(dp[i][j],dp[i][k]+dp[k+1][j])，3.更新後再看該縮寫中是否有重複的substring (0,k)，若有，再把dp[i][j]更新為substr.length()/repeatStr.length() + "[" + dp[i][i+k] + "]"

Pseudocode

String[][] dp = new String[s.length()][s.length()];

for(substring length from 0 to s.length())
    for(substring start index i from 0 to s.length())
        int j = substring end index
        check if substring length > 4
        for(k = the index that cut substring into half)
            dp[i][j] = min(dp[i][j],dp[i][k]+dp[k+1][j])

        for(find repeat pattern in substring)
            if repeat pattern found,
                dp[i][j]=substr.length()/repeatStr.length() + "[" + dp[i][i+k] + "]"

return dp[0][s.length()-1];

Code

class Solution {
    public String encode(String s) {
        String[][] dp = new String[s.length()][s.length()];

        for(int l=0;l<s.length();l++) {
            for(int i=0;i<s.length()-l;i++) {
                int j = i+l;
                String substr = s.substring(i, j+1);
                if(j - i < 4) {
                    dp[i][j] = substr;
                } else {
                    dp[i][j] = substr;
                    for(int k = i; k<j;k++) {
                        if((dp[i][k] + dp[k+1][j]).length() < dp[i][j].length()){
                            dp[i][j] = dp[i][k] + dp[k+1][j];
                        }
                    }

                    for(int k=0;k<substr.length();k++) {
                        String repeatStr = substr.substring(0, k+1);
                        if(repeatStr != null 
                           && substr.length()%repeatStr.length() == 0 
                           && substr.replaceAll(repeatStr, "").length() == 0) {
                              String ss = substr.length()/repeatStr.length() + "[" + dp[i][i+k] + "]";
                              if(ss.length() < dp[i][j].length()) {
                                dp[i][j] = ss;
                              }
                         }
                    }
                }
            }
        }

        return dp[0][s.length()-1];
    }
}

ref:https://leetcode.com/problems/encode-string-with-shortest-length/discuss/95599/Accepted-Solution-in-Java

Leetcode: Encode String with Shortest Length && G面经