How much slower does Java works on String than ArrayList?

Question

While doing LeetCode 125, I adopt a straightforward algorithm:

trim the string.
traverse the trimmed string to validate if it is a palindrome.

The trimmed string was stored as a String or an ArrayList. However, traversing the trimmed string (stored as a String) resulted in "Time Exceeded", while traversing the ArrayList was accepted. Since the two pieces of code were exactly the same except the String/ArrayList, I wonder it may be much slower while Java worked on String than ArrayList.

Could anyone tell me where does the difference come from?

Code 1 (by String) :

public class Solution {
    public boolean isPalindrome(String s) {
        s = s.toLowerCase();
        String trimmed = "";
        for (int i=0; i<s.length(); i++) {
            char ch = s.charAt(i);
            if (ch >= 'a' && ch <= 'z' || ch >= '0' && ch <= '9') {
                trimmed = trimmed + ch;
            }
        }

        for (int i=0; i<(trimmed.length()+1)/2; i++) {
            if (trimmed.charAt(i) != trimed.charAt(trimmed.length() -1 -i)) {
                return false;
            }
        }
        return true;
    }
}

Code 2, (by ArrayList):

public class Solution {
    public boolean isPalindrome(String s) {
        s = s.toLowerCase();
        List<Character> trimmed = new ArrayList<Character>();
        for (int i=0; i<s.length(); i++) {
            char ch = s.charAt(i);
            if (ch >= 'a' && ch <= 'z' || ch >= '0' && ch <= '9') {
                trimmed.add(ch);
            }
        }

        for (int i=0; i<(trimmed.size())/2; i++) {
            if (trimmed.get(i) != trimmed.get(trimmed.size() - 1 -i)) {
                return false;
            }
        }
        return true;
    }
}

If efficiency would be the main focus, you could easily fuse character validation into palindrome detection and avoid creating any temporary objects at all (essentially iterate from both ends, skipping rejected characters). — Durandal
– Durandal, Commented Mar 11, 2015 at 18:34
@Durandal. Thanks for you comment. I knew this algorithm was not good enough since it could be validated by traversing the original string once instead of creating a new trimmed one. I was curious about how did the performance difference come, for avoiding the same trap in the future. Still thanks for you comment. — M. Wu
– M. Wu, Commented Mar 11, 2015 at 18:45

chrylis -cautiouslyoptimistic- · Accepted Answer · 2015-03-11 18:30:06Z

6

Strings are immutable, so your first example is creating and discarding lots of instances all the time. You should at least use StringBuilder for assembling strings like that.

answered Mar 11, 2015 at 18:30

chrylis -cautiouslyoptimistic-

77.5k21 gold badges127 silver badges167 bronze badges

Sign up to request clarification or add additional context in comments.

4 Comments

Dave Newton Over a year ago

(I'd add that the byte code can be checked to see what's actually being used, since there are circumstances under which StringBuilder will be used.)

M. Wu Over a year ago

Thank you so much, chrylis. Now I get which part should I improve while coding on String.

chrylis -cautiouslyoptimistic- Over a year ago

@DaveNewton I very seriously doubt any compiler would optimize the loop into a builder; it's only relatively recently that some compilers moved to it for single-statement concatenation, and this is the sort of thing usually left to the JIT.

Dave Newton Over a year ago

@chrylis I think they explicitly don't do this inside a loop, it's likely creating a StringBuilder for the concat and setting the reference to the toString results. My point was that the OP can just check the code to see what's happening under the covers.

mk. · Accepted Answer · 2015-03-11 18:32:00Z

5

It's here:

    trimmed = trimmed + ch;

String concatenation is not cheap, so every time you do this you create a new String and copy an internal array. In the ArrayList example, when you write:

    trimmed.add(ch);

you do not create a new array every time. Use StringBuilder if you want similar performance for strings:

StringBuilder trimmed = new StringBuilder();
    ...
    trimmed.append(ch)

For your case, you might consider replacing all whitespace using the existing replace method:

String trimmed = s.replace(" ", "");

answered Mar 11, 2015 at 18:32

mk.

11.8k6 gold badges43 silver badges56 bronze badges

1 Comment

M. Wu Over a year ago

Thank you, mk. I would go to refer Java documents on String.

Collectives™ on Stack Overflow

How much slower does Java works on String than ArrayList?

2 Answers 2

4 Comments

1 Comment

Your Answer

Hot Network Questions

Collectives™ on Stack Overflow

2 Answers 2

4 Comments

1 Comment

Your Answer

Sign up or log in

Post as a guest

Related