Java在String上的工作速度比ArrayList慢多少？

Question

在做LeetCode 125时,我采用了一种简单的算法:

1. 修剪弦乐.
2. 遍历修剪过的字符串以验证它是否是回文.

修剪后的字符串存储为String或ArrayList.但是,遍历修剪后的字符串(存储为String)会导致"Time Exceeded",同时接受遍历ArrayList.由于除了String/ArrayList之外,两段代码完全相同,我想在Java处理String而不是ArrayList时可能要慢得多.

谁能告诉我差异来自哪里？

代码1(按字符串):

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

代码2,(由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

字符串是不可变的,因此您的第一个示例是始终创建和丢弃大量实例.你应该至少用它StringBuilder来组装这样的字符串.

Answer 2

它在这里:

    trimmed = trimmed + ch;

字符串连接并不便宜,因此每次执行此操作时都会创建一个新的String并复制一个内部数组.在ArrayList示例中,当您编写:

    trimmed.add(ch);

你不是每次都创建一个新的数组.StringBuilder如果您想要字符串的类似性能,请使用:

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

对于您的情况,您可以考虑使用现有replace方法替换所有空格:

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