Accepted Solution in Java


  • 50
    H

    This is the first question I have answered in Leetcode. I hope you guys will like my solution. The approach here is simple. We will form 2-D array of Strings.
    dp[i][j] = string from index i to index j in encoded form.

    We can write the following formula as:-
    dp[i][j] = min(dp[i][j], dp[i][k] + dp[k+1][j]) or if we can find some pattern in string from i to j which will result in more less length.

    Time Complexity = O(n^3)

    public 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);
                // Checking if string length < 5. In that case, we know that encoding will not help.
                if(j - i < 4) {
                    dp[i][j] = substr;
                } else {
                    dp[i][j] = substr;
                    // Loop for trying all results that we get after dividing the strings into 2 and combine the   results of 2 substrings
                    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];
                        }
                    }
                    
                    // Loop for checking if string can itself found some pattern in it which could be repeated.
                    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];
    }
    }

  • 13

    Clean solution. President elect approved.


  • 1

    Although I'm not entirely sure about the run time of your replaceAll call. The replaceAll could potentially take O(n) time? @StefanPochmann any idea about the complexity of this problem?


  • 1
    H

    Yeah. replaceAll() will take O(n) time, but substr.length()%repeatStr.length() == 0 reduces its chances to occur very frequently. If I was removing this condition, then it was getting TLE.


  • 1
    C

    Thats replace all is really clever


  • 14
    X

    Your solution is great! It's really helpful. I kinda stuck at how to split the string to get the pattern. After I saw how you do the DP part, I fixed my problem. Thx!

    Here is the version of my code, really similar to yours. I changed the find pattern part use the KMP algorithm. Hope it's a little helpful :)

    public class Solution {
        public String encode(String s) {
            if(s == null || s.length() <= 4) return s;
            
            int len = s.length();
            
            String[][] dp = new String[len][len];
            
            // iterate all the length, stay on the disgnose of the dp matrix
            for(int l = 0; l < len; l ++) {
                for(int i = 0; i < len - l; i ++) {
                    int j = i + l;
                    String substr = s.substring(i, j + 1);
                    dp[i][j] = substr;
                    if(l < 4) continue;
                    
                    for(int k = i; k < j; k ++) {
                        if(dp[i][k].length() + dp[k + 1][j].length() < dp[i][j].length()) {
                            dp[i][j] = dp[i][k] + dp[k + 1][j];
                        }
                    }
                    
                    String pattern = kmp (substr);
                    if(pattern.length() == substr.length()) continue; // no repeat pattern found
                    String patternEncode = substr.length() / pattern.length() + "[" + dp[i][i + pattern.length() - 1] + "]";
                    if(patternEncode.length() < dp[i][j].length()) {
                        dp[i][j] = patternEncode;
                    }
                }
            }
            
            return dp[0][len - 1];
        }
        
        private String kmp (String s) {
            int len = s.length();
            int[] LPS = new int[len];
            
            int i = 1, j = 0;
            LPS[0] = 0;
            while(i < len) {
                if(s.charAt(i) == s.charAt(j)) {
                    LPS[i ++] = ++ j;
                } else if(j == 0) {
                    LPS[i ++] = 0;
                } else {
                    j = LPS[j - 1];
                }
            }
            
            int patternLen = len - LPS[len - 1];
            if(patternLen != len && len % patternLen == 0) {
                return s.substring(0, patternLen);
            } else {
                return s;
            }
        }
    }
    

  • 0
    X

    @DonaldTrump Glad to see president :)


  • 0
    This post is deleted!

  • 0
    G

    for every divisor of the length of substr you perform an O(n) replaceAll. why is it O(n) then?


  • 0
    C

    Excellent solution !


  • 4
    I

    A different way to fill the dp array, column by column, 33ms, beats 99%.
    It is O(n^4). Yours is not O(n^3) either, replaceAll is not constant.

    int n = s.length();
    String[][] dp = new String[n][n];
    for (int j = 0; j < n; ++j) {
        int i = j;
        dp[i][j] = s.substring(j, j+1);
        for (int p = 0; p < i; ++p) {
            dp[p][j] = dp[p][j - 1] + dp[i][j];
        }
        for (i = j - 1; i + 1 >= j - i; --i) {
            String sub = s.substring(i + 1, j + 1); // s[i+1..j]
            for (int k = i - (j - i) + 1; k >= 0 && sub.equals(s.substring(k, k + j - i)); k -= j - i) {
                String str = Integer.toString((j + 1 - k) / (j - i)) + "[" + dp[i+1][j] + "]";
                if (str.length() < dp[k][j].length()) {
                    dp[k][j] = str;
                    for (int p = 0; p < k; ++p) {
                        if (dp[p][k - 1].length() + str.length() < dp[p][j].length()) {
                            dp[p][j] = dp[p][k - 1] + str;
                        }
                    }
                }
            }
        }
    }
    return dp[0][n-1];
    

  • 4

    Just a simple notice here:

    // dp[i][k].length() + dp[k+1][j].length()
    // is much faster than (dp[i][k] + dp[k+1][j]).length()
    // because s1 + s2 is O(n) time, s1.length() + s2.length() is O(1) time
    

  • 1
    S

    @XiaotingHong said in Accepted Solution in Java:

    patternLen

    Really nice idea of using KMP to find repeated pattern!


  • 0

    @XiaotingHong I understand the part you built the LPS array.

    But for this segment of the code , I could not understand . Could you give me some explanations.

    int patternLen = len - LPS[len - 1];
    if(patternLen != len && len % patternLen == 0) {
    return s.substring(0, patternLen);
    } else {
    return s;
    }


  • 0
    S

    @axieyangb

    you can refer to the good explanation at http://www.geeksforgeeks.org/find-given-string-can-represented-substring-iterating-substring-n-times/ which uses KMP to find repeated pattern.


  • 0
    T

    @axieyangb
    That part is to find the repeated part.
    For example, you have ABAB. Then LPS[len-1] = LPS[3] = 2
    patternLen = 2, s.substring(0,2) = AB. So you find the minimum repeated part and return it.


  • 0
    T
    This post is deleted!

  • 0
    T
    This post is deleted!

  • 0
    S

    @tian-ru please refer to this link http://www.geeksforgeeks.org/find-given-string-can-represented-substring-iterating-substring-n-times/.

    Notice that in int patternLen = len - LPS[len - 1];, so in your case, patternLen = 6 - 2 = 4. And 6 % 4 != 0, so the kmp() will return the string itself.


  • 0
    T

    @seaeidolon

    You are right. My mistake.

    Thank you!


Log in to reply
 

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