0

我的老师要求我们创建两种方法来确定字符串是否为回文。一个必须是递归方法，另一个必须是迭代方法，我已经弄清楚了迭代版本，但我不知道如何使它成为递归方法。欢迎任何和所有帮助。谢谢

static boolean isPalindrome(String s)
{
    String noSpaces = s.replaceAll("\\W", ""); //remove all non-word chars from string
    String revString = ""; //store reversed string 

    //for loop working from outter chars to inner
    //to reverse the string

    for(int i = 1; i <= noSpaces.length(); i++)
    {
        //if true add char to revString String 
        if(noSpaces.charAt(i - 1) == noSpaces.charAt(noSpaces.length() - i))
            revString = revString + noSpaces.charAt(i - 1);
    }

    //return true if original string matches reversed string
    if(noSpaces.equals(revString))
        return true;
    else
        return false;

}
4

3 回答 3

1

创建一个递归方法，它接受一个字符串并返回一个布尔值，就像迭代方法一样。

  • 它将检查第一个和最后一个字符，如果它们不同 return false，

  • 如果它们是同一个调用并返回方法，其中第一个和最后一个字符作为参数

  • 如果它是单个字符或空字符串，它将返回true。

关于迭代方法的提示：

  • 区分大小写重要吗？

  • 虽然您的方法是一种方法，但还有另一种方法只需要检查一半的字符串（而不是 from 1to noSpaces.length()）。

于 2013-04-03T22:54:18.733 回答
1

递归通过调用自身的方法工作。递归的一个著名例子是阶乘：n! = n * (n-1)!. 递归之所以有效，是因为输入每次都在变化；如果没有，它基本上将是一个无限循环占用内存并最终导致程序崩溃。关于递归的最后一件事：有一点答案是已知的，比如阶乘，0! = 1. 递归方法需要给出这个已知值的答案，否则它将继续运行，直到它崩溃或抛出错误（因为被问到不可能的事情）。在您的示例中，如果某事物具有一个字符或两个完全相同的字符，您就知道它是否是回文。

递归：您想要的方法是获取一个字符串，执行 replaceAll 以删除非单词字符，（添加一个 .toLowerCase() 到它），然后检查第一个和最后一个字符是否相同。如果是，则再次运行该方法，输入已noSpaces删除第一个和最后一个字符。但是，如果 String 的长度 <= 3 并且第一个和最后一个字符相同，那么您可以继续并返回 true。如果您不添加它，当您尝试删除不存在的字符时会出现错误（不过还有另一种方法）。

您的迭代方法很大，您可以将其缩小。您不需要检查所有字符，只需检查其中一半（如果您的长度为奇数，则为 1/2 + 1）。您也不需要复制字符串，而是在同一个字符串上使用两个 charAt 方法。

编辑：我确实删除了我的代码，因为这是家庭作业。如果你真的需要看，看一下编辑历史

于 2013-04-03T22:57:49.853 回答
1

试试这个：

public static boolean palindrome(String Str){
        if(Str.length()<=0)
            return true;
        if(Str.charAt(0)!=Str.charAt(Str.length()-1))
            return false;
        else
            return palindrome(Str.substring(1,Str.length()-1));
    }
于 2014-02-05T17:26:06.423 回答