Confused: trivial refactoring brings a TLE n^2 code to 22ms accepted code, beating 69%?


  • 0
    Y

    I used to have the following code, which checks each position with a left pointer and a right pointer. It is O(n^2) time complexity, and I got a TLE.

    Later I trivially refactored the duplicate code out into a function, shown below, and I got accepted with 22ms running time which beats 69% of Java solutions.

    Why such a big difference with a trivial refactoring? I resubmitted two versions for a few times and the result is consistent.

    public String longestPalindrome(String s) {
            // scan left and right, for each position i, examine the max
            // odd-length palindrome centered at i, and the the even-length
            // palindrome centered at i and i + 1
            String maxPalindrome = "";
            for (int i = 0; i < s.length(); i++) {
                // odd-length palindrome centered at i
                int left = i;
                int right = i;
                while (left >= 1 && right < s.length() - 1 && s.charAt(left - 1) == s.charAt(right + 1)) {
                    left--;
                    right++;
                }
                if (right - left + 1 > maxPalindrome.length()) {
                    maxPalindrome = s.substring(left, right + 1);
                }
                // even-length palindrome centered at i and i + 1
                if (i < s.length() - 1 && s.charAt(i) == s.charAt(i+1)) {
                    left = i;
                    right = i + 1;
                    while (left >= 1 && right < s.length() - 1 && s.charAt(left - 1) == s.charAt(right + 1)) {
                        left--;
                        right++;
                    }
                    if (right - left + 1 > maxPalindrome.length()) {
                        maxPalindrome = s.substring(left, right + 1);
                    }
                }
            }
            return maxPalindrome;
        }
    

    This is the new function I have:

    private String palindrome(String s, int currMax, int left, int right) {
        while (left >= 1 && right < s.length() - 1 && s.charAt(left - 1) == s.charAt(right + 1)) {
            left--;
            right++;
        }
        if (right - left + 1 > currMax) {
            return s.substring(left, right + 1);
        }        
        return null;
    }

  • 0
    G

    Are you sure the original code you supplied is accurate? I had a spookily similar answer to the refactored version of yours except that I accidentally had the character comparison portion of the while expression inside the loop in an if statement, which of course resulted in an infinite loop and caused a TLE. Although you're probably smarter than me and didn't make that mistake.


Log in to reply
 

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