java - 降低 isPalindrome 解决方案的复杂性？

Question

这是我的 isPalindrome 方法

public static boolean isPalindrome(String s){
    for(int i = 0; i < s.length()/2; i++){
        int j = s.length() - 1 - i;
        if(s.charAt(i) != s.charAt(j))
            return false;
    }
    return true;
}

我的老师说我可以降低复杂性，但我不知道该怎么做。我已经只经历了一半的字符串。有什么方法可以降低此解决方案的复杂性吗？

Answer 1

你可以尝试这样的事情:

public static boolean isPalindrome (String str) {
    int left = 0;
    int right = str.length() - 1;

    while (left < right) {
        if (str.charAt(left) != str.charAt(right))
            return false;
        left++;
        right--;
    }
    return true;
}

这样做的好处是不用每次循环都计算右边的索引，特别是因为它每次都必须访问字符串长度(这是常量)。

顺便说一句，我也倾向于更喜欢比 s、i 和 j 更有意义的变量名——我的基本规则是，如果您必须求助于 j，最好更明确地命名您的计数器(i 如果它是唯一的计数器就没问题)。