How much slower does Java works on String than ArrayList?

Question

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;
    }
}

Answer 1

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.