如何找到最长的回文子序列？-Java 学习之路

这是来自Algorithms book（Vazirani）的问题（6.7 ch6），与finding longest palindrome的经典问题略有不同 . 我怎么解决这个问题？

如果从左到右或从右到左阅读，则子序列是回文的 . 例如，序列A，C，G，T，G，T，C，A，A，A，A，T，C，G
具有许多回文子序列，包括A，C，G，C，A和A，A，A，A（另一方面，子序列A，C，T不是回文） . 设计一个算法，该算法采用序列x [1 ... n]并返回（最长的）最长的回文子序列 . 其运行时间应为O（n ^ 2）

8 回答

最长回归序列的Java实现

public class LongestPalindrome 
{
    int max(int x , int y)
    {
        return (x>y)? x:y;  
    }

    int lps(char[] a ,int i , int j)
    {
        if(i==j) //If only 1 letter
        {
            return 1;
        }
        if(a[i] == a[j] && (i+1) == j) // if there are 2 character and both are equal
        {
            return 2;   
        }
        if(a[i] == a[j]) // If first and last char are equal
        {
            return lps(a , i+1 , j-1) +2;
        }
        return max(lps(a,i+1 ,j),lps(a,i,j-1)); 
    }

    public static void main(String[] args) 
    {
        String s = "NAMAN IS NAMAN";
        LongestPalindrome p = new LongestPalindrome();
        char[] c = s.toCharArray();
        System.out.print("Length of longest seq is" + p.lps(c,0,c.length-1));           
    }
}

回复于 2024-05-02T06:24:58+08:00

private static int findLongestPalindromicSubsequence(String string) { 
    int stringLength = string.length();
    int[][] l = new int[stringLength][stringLength];
    for(int length = 1; length<= stringLength; length++){
        for(int left = 0;left<= stringLength - length;left++){
            int right = left+ length -1;
            if(length == 1){
                l[left][right] = 1;
            }
            else{  
                if(string.charAt(left) == string.charAt(right)){
                    //L(0, n-1) = L(1, n-2) + 2
                    if(length == 2){
                        // aa
                        l[left][right] = 2;
                    }
                    else{
                        l[left][right] = l[left+1][right-1]+2;
                    } 
                }
                else{
                    //L(0, n-1) = MAX ( L(1, n-1) ,  L(0, n-2) )
                    l[left][right] = (l[left+1][right] > l[left][right-1])?l[left+1][right] : l[left][right-1];
                } 
            }  
        }
    } 
    return l[0][stringLength-1];
}

回复于 2024-05-02T06:24:58+08:00

-2

该问题也可以作为称为LCS（最长公共子序列）问题的非常常见问题的变体来完成 . 让输入字符串由字符数组s1 [0 ... n-1]表示 .

1）反转给定的序列并将反向存储在另一个数组中，例如s2 [0..n-1]，其本质上是s1 [n-1 .... 0]

2）给定序列s1和反向序列s2的LCS将是最长的回文序列 .

该解决方案也是O（n ^ 2）解决方案 .

回复于 2024-05-02T06:24:58+08:00
1
对于字符串中的每个字母：
- 将字母设置为回文的中间（当前长度= 1）
- 如果这是它的中间，检查回文多长时间
- 如果这个回文比我们发现的回文长（直到现在）：保持索引和回文的大小 .
O（N ^ 2）：因为我们有一个循环选择中间和一个循环，检查回文多长时间，如果这是中间 . 每个循环从0到O（N）[第一个从0到N-1，第二个从0到（N-1）/ 2]

例如：D B A B C B A.

i = 0：D是回文的中间，不能超过1（因为它是第一个）

i = 1：B是回文的中间，在B之前和之后检查char：不相同（一侧为D而另一侧为A） - >长度为1 .

i = 2：A是回文的中间，在A之前和之后检查char：两个B - >长度为3.检查间隙为2的字符：不识别（一边为D，另一边为C） - >长度是3 .

等等
回复于 2024-05-02T06:24:58+08:00

这使得我对子串和子序列之间的差异感到有些困惑 . （见Ex6.8和6.11）根据我们对子序列的理解，给出的例子没有回文子序列ACGCA . 这是我的伪代码，我不太确定初始化> <

for i = 1 to n do
    for j = 1 to i-1 do
        L(i,j) = 0
for i = 1 to n do
    L(i,i) = 1
for i = n-1 to 1 do    //pay attention to the order when filling the table
    for j = i+1 to n do
        if x[i] = x[j] then
           L(i,j) = 2 + L(i+1, j-1)
        else do
           L(i,j) = max{L(i+1, j), L(i, j-1)}
return max L(i,j)

准备算法最终...

回复于 2024-05-02T06:24:58+08:00

import java.util.HashSet;

import java.util.Scanner;

/ ** * @param args 我们得到一个字符串，我们需要找到该字符串中最长的子序列，它是回文在这段代码中我们使用了hashset来确定给定字符串中唯一的子字符串集* /

公共类NumberOfPalindrome {

/**
     * @param args
     * Given a string find the longest possible substring which is a palindrome.
     */
    public static HashSet<String> h = new HashSet<>();
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        String s = sc.nextLine();
        for(int i=0;i<=s.length()/2;i++)
            h.add(s.charAt(i)+"");
        longestPalindrome(s.substring(0, (s.length()/2)+(s.length()%2)));
        System.out.println(h.size()+s.length()/2);
        System.out.print(h);
    }

    public static void longestPalindrome(String s){
        //System.out.println(s);
        if(s.length()==0 || s.length()==1)
            return;
        if(checkPalindrome(s)){
            h.add(s);
        }
        longestPalindrome(s.substring(0, s.length()-1));
        longestPalindrome(s.substring(1, s.length()));

    }
    public static boolean checkPalindrome(String s){
        //System.out.println(s);
        int i=0;int j=s.length()-1;
        while(i<=j){
            if(s.charAt(i)!=s.charAt(j))
                return false;
            i++;j--;
        }
        return true;
    }
}

回复于 2024-05-02T06:24:58+08:00

0

Input : A1，A2，....，An

Goal : 找到最长的严格增加的子序列（不一定是连续的） .

L(j): 最长的严格增加的子序列以j结尾

L(j): max{ L(i)}+1 } where i < j and A[i] < A[j]

然后找 max{ L(j) } for all j

你会得到源代码here

回复于 2024-05-02T06:24:58+08:00
-1
这可以使用动态编程在O（n ^ 2）中求解 . 基本上，问题是使用 x[i+1...j] ， x[i,...j-1] 和 x[i+1,...,j-1] 的最长子序列在 x[i...j] 中构建最长的回文子序列（如果第一个和最后一个字母相同） .

首先，空字符串和单个字符串通常是回文 . 请注意，对于子串 x[i,...,j] ，如果 x[i]==x[j] ，我们可以说最长回文的长度是 x[i+1,...,j-1]+2 上最长的回文 . 如果它们不匹配，则最长的回文最大值为 x[i+1,...,j] 和 y[i,...,j-1] .

这给了我们这个功能：
```
longest(i,j)= j-i+1 if j-i<=0,
              2+longest(i+1,j-1) if x[i]==x[j]
              max(longest(i+1,j),longest(i,j-1)) otherwise
```
您可以简单地实现该函数的memoized版本，或者编写一个最长[i] [j]自下而上的表 .

这只给出了最长子序列的长度，而不是实际的子序列本身 . 但它也可以很容易地扩展到这样做 .
回复于 2024-05-02T06:24:58+08:00

如何找到最长的回文子序列？

8 回答

相关问题