回文 StackOverflow 错误

Question

我尝试用递归来解决回文问题。我在线程 "main" java.lang.WhosebugError 中遇到异常在 java.lang.String.substring(String.java:1969) 在 Main.isPalindrome(Main.java:160)

但是，我不知道如何修复它。

public static boolean isPalindrome(String s) {
        int len = s.length();
        if (len <= 1) return true;
        else {
            char ch1 = Character.toLowerCase(s.charAt(0));
            char ch2 = Character.toLowerCase(s.charAt(len - 1));
            boolean check1 = Character.isLetter(ch1) || Character.isDigit(ch1);
            boolean check2 = Character.isLetter(ch2) || Character.isDigit(ch2);
            if (check1 && check2) {
                if (ch1 == ch2) {
                    String shorter = s.substring(1, len - 1);
                    return isPalindrome(shorter);
                }
                else {
                    return false;
                }
            }
            else if (!check1 && check2) {
                String shorter = s.substring(1);
                return isPalindrome(shorter);
            }
            else if (!check2 && check1) {
                String shorter = s.substring(0, len - 1);
                return isPalindrome(shorter);
            }
            else {
                String shorter = s.substring(1, len - 1);
                return isPalindrome(shorter);
            }
        }
    }

Answer 1

很难说不知道哪一行是 160。也就是说，您可能使用与方法本身相同的参数调用它，因此没有什么可以结束递归。

Answer 2

你的逻辑没有问题。只是用于保存堆栈帧的内存量有限，因此递归级别的数量有限。当输入字符串足够大时，将抛出 WhosebugError。

我的建议是放弃这种递归实现，改用循环。

回文 StackOverflow 错误

palindrome StackOverflow Error

java

algorithm

recursion

palindrome