Leetcode 234. Palindrome Linked List, String solution gives time exceeded error, can anyone explain why?

Question

This is the solution i have given.

class Solution {

    public boolean isPalindrome(ListNode head) {
       String s= "";
       String p= "";
        while(head != null){
            s= s+head.val;
            p = head.val+p;
            head = head.next;
        }
        return s.equals(p);
    }
}

I can understand i am creating multiple strings in string pool. but it doesnt show memory exceeded. it shows "Testcases passed, but took too long."

Can someone kindly explain how is that exceeding time limit whereas all the other solutions has minmum of two loops? be it two pointer solution or the list solution or the stack solution.

I was expecting it to run properly, because I am just using one loop to create both the reverse and normal string and as far as i know equals is a O(1) process. So how does the time limit exceeds?

String concatenation would be slower than using a StringBuilder. Equals check has to compare every character, though, so it's not constant time — OneCricketeer
– OneCricketeer, Commented Apr 6, 2024 at 20:39
Be aware that you could get false positives, like with 1→11 which is not a palindrome, but your function will determine it is. — trincot
– trincot, Commented Apr 6, 2024 at 20:45
For reference, the page for LeetCode 234 is leetcode.com/problems/palindrome-linked-list/description — Old Dog Programmer
– Old Dog Programmer, Commented Apr 6, 2024 at 22:46

trincot · Accepted Answer · 2024-04-06 21:42:30Z

I am just using one loop to create both the reverse and normal string and as far as i know equals is a O(1) process.

It is not, but that is not the problem. The slowdown is in the loop body. Both s+head.val and head.val+p are expressions that need to visit each character in the involved strings, and so they have a O(𝑛) time complexity where 𝑛 is the current size of s or p respectively. And this gives a total time complexity that is O(𝑛²).

To improve on this, use StringBuilder, whose append method has an amortised time complexity of O(1). Don't build p in the loop, only s, and reverse s at the end of the loop:

class Solution {
    public boolean isPalindrome(ListNode head) {
        StringBuilder s = new StringBuilder();
        while (head != null) {
            s.append(head.val);
            head = head.next;
        }
        return s.toString().equals(s.reverse().toString());
    }
}

This has the optimal -- O(𝑛) -- time complexity.

Note that this would not work if the values of the nodes could have multiple characters (when turned to string representation). But as the code challenge specifies in its constraints section that the values are single digit numbers, this is not an issue.

The auxiliary space complexity of this solution O(𝑛). A next challenge would be to solve this problem with just O(1) auxiliary space complexity...

Collectives™ on Stack Overflow

Leetcode 234. Palindrome Linked List, String solution gives time exceeded error, can anyone explain why?

1 Answer 1

Comments

Your Answer

Hot Network Questions

Collectives™ on Stack Overflow

1 Answer 1

Comments

Your Answer

Sign up or log in

Post as a guest

Related