Use StringBuffer will cause "Time limit exceeded"


  • 1
    C

    Be careful of using StringBuffer to reconstruct the string, although it seems to be O(N) it will cause time limit exceed:
    My original code exceeded run time:

    """
    public class Solution{
    public String longestPalindrome(String s){
    if(s == null || s.length() == 0) return s;
    int n = s.length();
    boolean[][] mem = new boolean[n][n];

        int[] index = new int[2];
        int max = 0;
        
        // two types of base cases;
        for(int i = 0; i < n; i++){
            mem[i][i] = true;
            index[0] = i;
            index[1] = i;
        }
        
        for(int i = 0; i < n - 1; i++){
            if(s.charAt(i) == s.charAt(i + 1)){
                int temp = i  + 1;
                mem[i][i + 1] = true;
                //System.out.println(i + " " + temp + " " + mem[i][i + 1]);
                index[0] = i;
                index[1] = i + 1;
            }
        }
        
        for(int len = 3; len <= n; len++){
            for(int i = 0; i < n - len + 1; i++){
                int j = i + len - 1;
                //System.out.println(i + " " + j + " " + mem[i + 1][j - 1]);
                mem[i][j] = s.charAt(i) == s.charAt(j) && mem[i + 1][j - 1];
                if(mem[i][j]){
                    int pre = max;
                    max = Math.max(max, j - i + 1);
                    //System.out.println(i + " " + j);
                    if(max > pre){
                        index[0] = i;
                        index[1] = j;
                    }
                } 
            }
        }
        
        StringBuffer buffer = new StringBuffer();
        for(int i = index[0]; i <= index[1]; i++){
            buffer.append(s.charAt(i));
        }
        return buffer.toString();
        
            
    }
    

    }
    """

    After I abandoned the StringBuffer part, and used one substring, code is still O(N^2) and passed all tests.

    """
    public class Solution{
    public String longestPalindrome(String s){
    if(s == null || s.length() == 0) return s;
    int n = s.length();
    boolean[][] mem = new boolean[n][n];

        int[] index = new int[2];
        int max = 0;
        
        // two types of base cases;
        for(int i = 0; i < n; i++){
            mem[i][i] = true;
            index[0] = i;
            index[1] = i;
        }
        
        for(int i = 0; i < n - 1; i++){
            if(s.charAt(i) == s.charAt(i + 1)){
                int temp = i  + 1;
                mem[i][i + 1] = true;
                index[0] = i;
                index[1] = i + 1;
            }
        }
        
        for(int len = 3; len <= n; len++){
            for(int i = 0; i < n - len + 1; i++){
                int j = i + len - 1;
                mem[i][j] = s.charAt(i) == s.charAt(j) && mem[i + 1][j - 1];
                if(mem[i][j]){
                    int pre = max;
                    max = Math.max(max, j - i + 1);
                    if(max > pre){
                        index[0] = i;
                        index[1] = j;
                    }
                } 
            }
        }
        
       return s.substring(index[0], index[1] + 1);
            
    }
    

    }
    """


  • 0
    M

    @chunyans said in Use StringBuffer will cause "Time limit exceeded":

    Use StringBuffer will cause "Time limit exceeded"
    using StringBuffer [...] will cause time limit exceed

    Then why did I just get your StringBuffer solution accepted? In my first submission of it?

    I then also submitted your second solution and that exceeded the time limit.

    How often did you submit each?

    Btw, please format your code properly.


  • 2
    C

    Thanks for checking my solutions!
    However after double checking the stringBuffer solution exceeded, and substring solution passed.
    0_1499821466949_671f2b3e-3f28-4449-821e-e6e34e9f6a1c-image.png

    0_1499821552814_7140421c-45da-4ea2-8e2f-f7707f192449-image.png


Log in to reply
 

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