尽管不是堆栈的一部分，但字符串中最长回文的输出得到正确打印

Question

我写了一些代码来查找字符串中最长的回文（回文不必一起出现，因为它可以是不连续的）

几乎适用于所有情况。对于下面代码中的情况，它确实打印出正确的回文及其长度。但是，有一个问题让我感到困惑。我有一个名为 compare() 的函数，在这里我将新发现的回文长度与 'longestPalindromeLength' 的长度进行比较，想法是，当所有辅助函数 return 返回主函数时，静态（全局）名为 'longestPalindromeString' 的变量将具有结果。

我的问题是，当我打印这个 compare() 函数时，我没有看到最长的回文，即 "ABCDEEEEDCBA" 中的任何地方。

请看我的代码

public class LongestPalindromeNonContiguousPrint
{
    //static String S = "abcdcba";
    //static String S = "SGEGGES";
    static String S = "SGEGGESABCDEEEEDCBA";
    //static String S = "abca1221";

    static int longestPalindromeLength = 0;
    static String longestPalindromeString = "";

    public static void main(String[] args)
    {
        System.out.println("Length of the longest palindrome == " + fun(0, S.length()-1,""));
        System.out.println("Longest palindrome == "+longestPalindromeString);
    }

    static int fun(int s, int e, String palindrome)
    {
        String temp = "";

        /* base cases for even */
        if(s == e-1)
        {
            if(S.charAt(s) == S.charAt(e))
            {
                palindrome = palindrome + S.charAt(s);
                compare(palindrome,"even");
                return 2;
            }

            else
            {
                palindrome = palindrome + S.charAt(s);
                compare(palindrome,"odd");
                return 1;
            }
        }

        /* base case for odd */
        if(s == e)
        {
            palindrome = palindrome + S.charAt(s);
            compare(palindrome,"odd");
            return 1;
        }

        /*if(s > e)
            return (S.charAt(s-1) == S.charAt(e+1)) ? 1:0;*/

        /* recurse */
        if(S.charAt(s) == S.charAt(e))
        {
            palindrome = palindrome + S.charAt(s);

            temp = palindrome;
            int rec = fun(s+1, e-1, palindrome);
            palindrome = temp;

            int ret = 2 + rec;
            return ret;
        }

        else 
        {
            temp = palindrome;
            int rec1 = fun(s+1, e, palindrome);
            palindrome = temp;

            temp = palindrome;
            int rec2 = fun(s, e-1, palindrome);
            palindrome = temp;

            return max(rec1, rec2);
        }
    }

    static int max(int a, int b)
    {
        if(a > b)
            return a;
        return b;
    }

    static void compare(String s, String type)
    {
        String palindrome = "";
        String rev = new StringBuilder(s).reverse().toString();

        if(type == "odd")
        {
            palindrome = s + rev.substring(1,rev.length());
        }

        else if(type == "even")
        {
            palindrome =  s + rev;
        }

        if(palindrome.length() > longestPalindromeLength)
        {
            longestPalindromeLength = palindrome.length();
            longestPalindromeString = palindrome;

            /* This does not get printed, I do not understand where this print() function
             * sees this string ABCDEEEEDCBA */
            if(longestPalindromeString == "ABCDEEEEDCBA")
            {
                System.out.println("found ABCDEEEEDCBA");
            }
        } 
    }
}

输出

Length of the longest palindrome == 12
Longest palindrome == ABCDEEEEDCBA

请看一下 compare() 函数，我已经插入了一个 if 条件来打印 "ABCDEEEEDCBA" 当它是最长回文时。但它永远不会达到这个条件。

编辑：如果输出太大，是否会遮蔽 trim 一些输出。对于下面的程序，我观察到 eclipse 和终端的运行之间的输出存在差异。运行在 eclipse 上给我 24811 行输出，但是运行从终端给我 47769 输出。

public class LongestPalindromeNonContiguousPrint
{
    //static String S = "abcdcba";
    //static String S = "GEEKSFORGEEKS";
    //static String S = "SGEGGES";
    static String S = "SGEGGESABCDEEEEDCBA";
    //static String S = "abca1221";

    static int longestPalindromeLength = 0;
    static String longestPalindromeString = "";

    public static void main(String[] args)
    {
        System.out.println("Length of the longest palindrome == " + fun(0, S.length()-1,""));
        System.out.println("Longest palindrome == "+longestPalindromeString);
    }

    static int fun(int s, int e, String palindrome)
    {
        String temp = "";

        /* base cases for even */
        if(s == e-1)
        {
            if(S.charAt(s) == S.charAt(e))
            {
                palindrome = palindrome + S.charAt(s);
                compare(palindrome,"even");
                return 2;
            }

            else
            {
                palindrome = palindrome + S.charAt(s);
                compare(palindrome,"odd");
                return 1;
            }
        }

        /* base case for odd */
        if(s == e)
        {
            palindrome = palindrome + S.charAt(s);
            compare(palindrome,"odd");
            return 1;
        }

        /*if(s > e)
            return (S.charAt(s-1) == S.charAt(e+1)) ? 1:0;*/

        /* recurse */
        if(S.charAt(s) == S.charAt(e))
        {
            palindrome = palindrome + S.charAt(s);

            temp = palindrome;
            int rec = fun(s+1, e-1, palindrome);
            palindrome = temp;

            int ret = 2 + rec;
            return ret;
        }

        else 
        {
            temp = palindrome;
            int rec1 = fun(s+1, e, palindrome);
            palindrome = temp;

            temp = palindrome;
            int rec2 = fun(s, e-1, palindrome);
            palindrome = temp;

            return max(rec1, rec2);
        }
    }

    static int max(int a, int b)
    {
        if(a > b)
            return a;
        return b;
    }

    static void compare(String s, String type)
    {
        String palindrome = "";
        String rev = new StringBuilder(s).reverse().toString();

        if(type == "odd")
        {
            palindrome = s + rev.substring(1,rev.length());
        }

        else if(type == "even")
        {
            palindrome =  s + rev;
        }

        System.out.println(palindrome);

        if(palindrome.length() > longestPalindromeLength)
        {
            longestPalindromeLength = palindrome.length();
            longestPalindromeString = palindrome;

            /*if(palindrome.equals("ABCDEEEEDCBA"))
            {
                System.out.println("found ABCDEEEEDCBA");
            }*/
        } 
    }
}

Answer 1

您正在使用 == 而不是 String 的 equals 方法比较字符串。

尽管不是堆栈的一部分，但字符串中最长回文的输出得到正确打印

Output of longest palindrome in a string gets printed correctly in spite of not being part of stack

java

recursion

dynamic-programming

longest-substring