share my java solution!


  • 0
    T
    class Solution {
        public String encode(String s) {
            if(s==null || s.length()<=4){
                return s;
            }
            String[][] dp = new String[s.length()][s.length()];
            
            return dfs(dp,s,0,s.length()-1);
        }
        
        public String dfs(String[][] dp,String str,int start,int end){
            if(dp[start][end]!=null){
                return dp[start][end];
            }
            if(end-start+1<=4){
                return str.substring(start,end+1);
            }
            
            String temp_str = str.substring(start,end+1);
            dp[start][end] = temp_str;
            for(int i=start;i<end;i++){
                String t1 = dfs(dp,str,start,i);
                String t2 = dfs(dp,str,i+1,end);
                int len = t1.length()+t2.length();
                if(len<dp[start][end].length()){
                    dp[start][end]=t1+t2;
                }
            }
            
            String pattern = findpattern(temp_str);
            if(pattern.length()>=dp[start][end].length()){
                return dp[start][end];
            }
            
            String target = temp_str.length()/pattern.length() + "["+dfs(dp,str,start,start+pattern.length()-1)+"]";
            
            if(target.length()>=dp[start][end].length()){
                return dp[start][end];
            }else{
                dp[start][end]=target;
                return target;
            }
            
        }
        
        public String findpattern(String str){
            char[] array = str.toCharArray();
            int i=0;
            int j=1;
            int[] dp = new int[array.length];
            dp[0]=0;
            while(j<array.length){
                if(array[i]==array[j]){
                    i++;
                    dp[j]=i;
                    j++;
                }else{
                    if(i!=0){
                        i=dp[i-1];
                    }else{
                        dp[j]=0;
                        j++;
                    }
                }
            }
            
            if(dp[array.length-1]!=0&&str.length()%(array.length-dp[array.length-1])==0){
                return str.substring(dp[array.length-1]);
            }
            return str;
        }
    }
    

Log in to reply
 

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