1

我在 C# 中实现了以下两种方法

private static string FindLongestPalindrome(string s) 
{
    string largest = "";

    for (int i = 1; i < s.Length-1; i++)
    {
        for (int j = i+1; j <= s.Length; j++)
        {
            if (IsPalindrome(s.Substring(i, j)))
            {
                largest = s.Substring(i, j);
            }
        }
    }

    return largest;
}

private static bool IsPalindrome(string s)
{
    bool isPalindrome = true;
    int j = s.Length-1;

    for (int i = 0; i < s.Length; i++)
    {
        if (s[i].ToString().ToLower() != s[j].ToString().ToLower())
        {
            isPalindrome = false;
            break;
        }

        j--;
    }

    return isPalindrome;
}

IsPalindrome检查字符串是否为回文，并FindLongestPalindrome找出字符串中最长的回文。是的，我意识到这FindLongestPalindrome不是最有效的并且是二次的。不过，我目前对此并不担心。我只是想知道为什么程序在以下点不断超出范围并抛出异常：

if (IsPalindrome(s.Substring(i, j))) {...}

如何修改这部分，以使每个字符串输入的代码都不会超出范围？

4

3 回答 3

2

It's because of this : 

for (int j = i+1; j <= s.Length; j++)

it should be :

for (int j = i+1; j < s.Length; j++)
于 2013-11-15T03:27:19.107 回答
1

您的问题是您试图从子字符串中检索太多字符。

你的 for 循环：

for (int j = i+1; j <= s.Length; j++)

应该：

for (int j = i; j <= s.Length - i; j++)

注意s.Length - i.

您的后续行：

if (IsPalindrome(s.Substring(i, j)))

你的第一个代码会失败，因为如果i是2，你最终会请求：s.Substring(2, s.Length)它将尝试检索比字符串中剩余的字符更多的字符。真的，您想要（我认为）获取字符串的其余部分，好吧，您可以保持原样，或者只使用从该索引开始的String.Substring(int)重载并抓取字符串的其余部分。编辑：不，对不起，这是一个坏主意，并且在某些测试中失败了。

不幸的是，您的代码中还有其他一些错误。例如，“banana”返回“ana”而不是“anana”。此外，如果最长回文以您输入的第一个字母开头，它会忽略它（因为您从 0 开始i = 1而不是从 0 开始）这里有一个固定版本：

private static string FindLongestPalindrome(string s) 
{
    string largest = "";

    //start at i = 0 instead
    //Also needs to be to i < s.Length or fails some tests
    for (int i = 0; i < s.Length; i++)
    {
        for (int j = i; j <= s.Length-i; j++)
        {
            string substring = s.Substring(i, j);

            //you also need to check that you're looking at a longer string
            //this really could be optimized anyway, but here it is for simplicity
            if (substring.Length > largest.Length && IsPalindrome(substring))
            {
                largest = substring;
            }
        }
    }

    return largest;
}

有了这个，一些测试：

banana --> anana
bananab --> bananab
zzz --> zzz
abcdddeeedddc --> cdddeeedddc
a --> a
abcbabbbbbbab --> babbbbbbab
于 2013-11-15T03:54:42.747 回答
1

c#不是c++吗……

   public static bool IsPalindrome(string s)
   {
      return s == new string(s.Reverse().ToArray());
   }

建议，将此添加为字符串的扩展方法

public static class StringSupport
{
    public static bool IsPalindrome(this string s)
    {
        return s == new string(s.Reverse().ToArray());
    }
}

用作此

bool palindrome = "string".IsPalindrome();
于 2013-11-15T03:33:21.533 回答