判断输入的字符串是否为回文的高效方法

Question

我最近写了一个简单的方法来判断一个字符串是否是回文。我想知道如何让它更加高效，肯定有一些内置函数可以加速计算。

感谢大家的帮助！

boolean checkPalindrome(String inputString) {

    ArrayList<Character> arrFront = new ArrayList<Character>();
    ArrayList<Character> arrBack = new ArrayList<Character>();

    for(int i=0; i<inputString.length()-1; i++) {
        arrFront.add(inputString.charAt(i));
    }

    for(int i=inputString.length()-1; i>0; i--) {
        arrBack.add(inputString.charAt(i));
    }

    StringBuilder builder1 = new StringBuilder(arrFront.size());
    for (Character c : arrFront) {
        builder1.append(c);
    }
    String front = builder1.toString();

    StringBuilder builder2 = new StringBuilder(arrBack.size());
    for (Character c : arrBack) {
        builder2.append(c);
    }
    String back = builder2.toString();

    return(front.equals(back));
}

- user9237783

---

“加速”是什么意思？时间复杂度，还是更少的代码？ - ZhaoGang

你的意思是像这样吗？请注意，这种方法代码更少，但效率不高。 - GBlodgett

我投票将此问题关闭，因为它应该在 Code Review SE 上被讨论。 - Andrey Tyukin

@AndreyTyukin 是的，如果你关心效率，那么简单的循环解决方案(for (int i = 0; i < n/2; ++i) { if (str.charAt(i) != str.charAt(n-i-1)) return false; })是更好的选择。 - GBlodgett

@GBlodgett 使用 str.length() 也会加快速度！提前返回将节省时间。 - Glains

@Glains 这就是代码中 n 代表的含义。它被解析为一个变量，以避免在循环的每次迭代中调用两次 length() 方法。 - GBlodgett

Answer 1

在效率方面，不总是使用内置函数和库（尽管在许多情况下它们是最佳选择）。但有时像这样的简单循环可能是最简单和有效的方法：

private boolean checkPalindrome(String inputString) {
    for(int i = 0, j = inputString.length() - 1; i < j; i++, j--) {
        if(inputString.charAt(i) != inputString.charAt(j)) {
            return false;
        }
    }
    return true;
}

- Mohamed Elsayed

Answer 2

可以参考@FernandoPelliccioni的文章检查回文字符串。他对这个解决方案进行了非常彻底的分析。

对于简单的解决方案：

public static boolean isPalindrome(String str) {
    return str.equals(new StringBuilder(str).reverse().toString());
}

就效率而言：

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

- m fauzan abdi

Answer 3

这里有一个更简单的方法。

public boolean checkPalindrome(String str) {
    int len = inputString.length()/2;
    for(int i = 0 ; i < len ; i++) {
        if(str.charAt(i) != str.charAt(str.length()-1-i)) {
            return false;
        }
    }
    return true;
}

当字符串的长度为N时。时间复杂度为O(N/2)。 注意：当字符串的长度为奇数时，不需要检查中间字符，因为它本身就是中间字符。

例如：

在ssstsss中，您不需要检查t。

由于len是int类型。不能表达小数部分。它会自动舍去。 ssstsss的长度为3，因为它是7/2 = 3.5，并且舍去了0.5。

即使长度为偶数，它也可以正常工作。例如，abccba。长度为6，len为3。当长度为偶数时，必须检查中间的两个字符，即cc。

- c-an

Answer 4

我认为最简单的方法是使用默认的StringBuilder类。这个类有一个很好的函数，可以派上用场。它被称为reverse()。它做了它所说的事情，它将传递到StringBuilder中的字符串反转。通过这种方式，很容易检查给定的字符串是否等于反转后的字符串。

例如，您可以执行以下操作：

public boolean isPallindrome(String input){
    StringBuilder reversed = new StringBuilder(input);
    reversed.reverse();
    /*
     * Just replace equals with equalsIgnoreCase
     * to ignore the case
     */
    return(reversed.toString().equalsIgnoreCase(input));
}

给定的代码只是创建了一个 StringBuilder 实例并直接附加输入。然后它反转了 StringBuilder 并检查输入是否等于反转后的字符串。

- Rias