CODEWITHSUNDEEP
javastringperformancearraylistjvm
M. Wu
M. Wu

Reputation: 159

How much slower does Java works on String than ArrayList?

While doing LeetCode 125, I adopt a straightforward algorithm:

  1. trim the string.
  2. 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;
    }
}

Upvotes: 4

Views: 71

Answers (2)

mk.
mk.

Reputation: 11710

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(" ", "");

Upvotes: 5

chrylis -cautiouslyoptimistic-
chrylis -cautiouslyoptimistic-

Reputation: 77187

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.

Upvotes: 6

Related Questions