使用递归检查字符串是否回文？

Question

使用递归检查字符串是否回文？

3

我的代码有问题，因为我作业中的一个测试用例出现了错误，在我提交代码在线上时出现了运行时错误。那个测试用例可能是任何字符串。我相信代码没有问题，因为我已经手动检查了很多个测试用例。

以下是代码：

public static boolean isStringPalindrome(String input) {
    if(input.length()==0 || input.length()==1)
        return true;

    int first = 0;
    int last = input.length()-1;

    if(input.charAt(first) != input.charAt(last))
        return false;

    String str="";
    for(int i=first+1;i<last;i++){
        str = str+input.charAt(i); 
    }
    boolean sa = isStringPalindrome(str);
    return sa; 
}

样例输入

racecar

输出

true

样例输入

pablo

输出

false

- Prince Vijay Pratap

你遇到了运行时错误？我很惊讶！你能发一下你具体遇到的错误吗？ - Wasi Ahmad

@WasiAhmad 在线工具并没有说明，它只显示了简单的消息“运行时错误（NZEC）”。 - Prince Vijay Pratap

我已经更新了我的答案，我在你的代码中没有发现任何问题，除了一个“null”字符串检查。你可以尝试添加那个条件。 - Wasi Ahmad

2个回答

2

检查回文的更简单方法可以是：

public static boolean isPalindrome(String s)
{   if (input == null)
        return false;
    else if(s.length() == 0 || s.length() == 1)
        return true;

    /* check for first and last char of String:
     * if they are same then do the same thing for a substring
     * with first and last char removed. and carry on this
     * until you string completes or condition fails.
     */
    if(s.charAt(0) == s.charAt(s.length()-1))
        return isPalindrome(s.substring(1, s.length()-1));

    return false;
}

更新

你遇到了运行时错误(NZEC)，这意味着非零退出代码。这意味着你的程序意外地结束了。我没有看到除了你的程序没有null检查之外的任何原因。否则，我仔细阅读了你的代码，你正在做我建议的相同的事情。

- Wasi Ahmad

我也在做那个，但不知何故我的代码在一个测试用例上无法工作，我不知道是哪个用例？ - Prince Vijay Pratap

你找到任何测试用例导致你的代码无法工作了吗？ - Wasi Ahmad

没有发现任何测试用例，尽管检查了许多不同的测试用例，而且所有的都似乎工作正常。 - Prince Vijay Pratap

网页内容由stack overflow 提供, 点击上面的

可以查看英文原文，
原文链接

- Elliott Frisch · Accepted Answer

你的代码在递归测试字符串是否为回文时似乎过于复杂。可以使用如下方式：

public static boolean isStringPalindrome(String input) {
    if (input == null) {
        return false;
    } else if (input.isEmpty() || input.length() == 1) {
        return true;
    }
    int len = input.length() - 1;
    return input.charAt(0) == input.charAt(len) //
            && isStringPalindrome(input.substring(1, len));
}

递归是不需要嵌套 for 循环的。如果你能这样做，应该像这样处理：

public static boolean isStringPalindrome(String input) {
    if (input == null) {
        return false;
    } else if (input.isEmpty() || input.length() == 1) {
        return true;
    }
    int len = input.length();
    for (int i = 0; i <= len / 2; i++) {
        if (input.charAt(i) != input.charAt(len - 1 - i)) {
            return false;
        }
    }
    return true;
}