8

给定一个包含字符 [AZ] 的长度为 N 的字符串，我如何确定单个字符的最长回文？

我将用一个例子来说明这一点：

给定字符串：JOHNOLSON 在分析字符串时，我们发现我们有一个带有字符的回文，O使得字符串看起来像。的回文长度为 7，基本上看起来像. 另外，请注意有一个带有 的回文，但它的长度仅为 6。JOHNOLSONOO--O--ON

另一个例子，Given string:ABCJOHNOLSON给出与上面相同的结果O，长度为 7 的回文看起来像。O--O--O

但是，对于给定的字符串ABCJOHNOLSONDA，最长的单个字符回文长度为 14，字符A看起来像。A------------A

其他简单的例子包括：

ABA--> (长度 3)A-A

ABAXYZ--> (长度 3)A-A

ABAXYZA--> （长度 5），不是长度 7，因为不是回文字母。A---AA-A---AA

请特别注意最后一个示例，因为它说明了问题的细微差别之一。

4

3 回答 3

5

您可以在线性时间内完成，此处使用代码示例进行了描述。

于 2011-11-20T19:02:04.103 回答
0

绝对不是最优的。假设输入字符串都是小写的。

using System;
using System.Collections.Generic;

public class LongestPalindrome
{
    public int longest(string s)
    {
        Dictionary<char, List<int>> indices = 
            new Dictionary<char, List<int>>();

        // find all indices for each letter
        for (int i = 0; i < s.Length; i++)
        {
            char c = s[i];
            if (!indices.ContainsKey(c)) 
                    indices.Add(c, new List<int>());
            indices[c].Add(i);
        }

        int max = Int32.MinValue;

        for (int i = (int)'a'; i <= (int)'z'; i++)
        {
            char c = (char)i;

            // in case a letter didn't appear at all in the input string
            if (!indices.ContainsKey(c)) continue;

            List<int> indexList = indices[c];

            // in case a letter appeared only once in the input string
            if (indexList.Count == 1) max = Math.Max(max, 1);

            for (int j = 0; j < indexList.Count; j++)
            {
                for (int k = j + 1; k < indexList.Count; k++)
                {
                    int dist = indexList[k] - indexList[j] + 1;
                    string sub = s.Substring(indexList[j], dist);
                    if (isPalendrome(sub, c)) 
                                        max = Math.Max(max, dist);
                }   
            }
        }

        return max;
    }

    bool isPalendrome(string s, char c)
    {
        int i = 0;
        while(i < s.Length - 1 - i) 
        {
            if (s[i] != c && s[s.Length - 1 - i] != c) 
            {
                i++;
                continue;   
            }
            if (s[i] != s[s.Length - 1 - i]) return false;
            i++;
        }
        return true;
    }
}
于 2011-11-20T20:41:01.093 回答
0

这是我想出的，我不知道它的效率如何。

对于字母表中的每个字母，
    查找此字母的第一个和最后一个匹配项。
    虽然子字符串不是该字母的回文（易于检查），
    找到两边的下一个字母，这样每个可能的组合都是
    检查。取最长的一个并存放它。
取最长的一个。
于 2011-11-20T19:02:57.850 回答