I can't understand why this code runs TLE


  • 0

    TLE test case is "a......a".
    My solution is find same letter and test whether it is palindrome, record the longest result and length instead of wasting time.
    As running with my code, just do following things:

    • test first and last letter 'a' and 'a', just equal;
    • test whether it is a palindrome string using function isPalindrome;
    • any other loop will be stopped by (j - i > max)

    Could someone tell me why it runs TLE.

    class Solution { 
        public String longestPalindrome(String s) {
            String result = "";
            int max = 0;
            for(int i = 0; i < s.length(); i++){
                for(int j = s.length(); j > i && j - i > max; j--){
                    if(s.charAt(i) == s.charAt(j - 1) && isPalindrome(s.substring(i, j))){
                        max = j - i;
                        result = s.substring(i, j);
                    }
                }
            }
            return result;
        }
        public boolean isPalindrome(String str){
            for(int i = 0; i < str.length() / 2; i++)
                if(str.charAt(i) != str.charAt(str.length() - 1 - i))
                    return false;
                
            return true;
        }
    }

  • 0
    F

    The problem here is the test case only looks like aaaaa...aaaa -- in reality, it probably has something in the middle.
    Try to apply your code (in your head) to case aaa...aaabcaaa...aaa (499 'a's, followed by 'bc', then by another 499 'a's)

    Spoiler:

    your code will take a pretty long time on this because "bc" in the middle makes the 'a's at the edges non-palindromic -- so your code will test 1000 chars at i==0, then 999 chars at i==1, and so on

    HTH


  • 0
    Y
    This post is deleted!

Log in to reply
 

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