algorithm - 如何打印最长回文子序列？如果有多个 LPS，我们需要打印从最低索引开始的一个

Question

这是我的代码，它可以正确打印 LPS，但如果存在多个 LPS，则无法打印从最低索引开始的代码。我尝试在 dp[i][j-1]==dp[i-1][j] 时单独处理一个案例，但由于某种原因也不起作用。任何帮助将不胜感激。

public class Solution { 
public static String longestPalinSubstring(String str) {
    String rev = reverse(str);
    int n = str.length();
    int[][] dp = new int[n+1][n+1];
    
    for(int i=1;i<=n;i++){
        for(int j=1;j<=n;j++){
            if(str.charAt(i-1)==rev.charAt(j-1)){
                dp[i][j] = 1 + dp[i-1][j-1];
            }else{
                dp[i][j] = Math.max(dp[i-1][j], dp[i][j-1]);
            }
        }
    }
    int i=n, j=n;
    String ans="";
    while(i>0 && j>0){
        if(str.charAt(i-1)==rev.charAt(j-1)){
            ans+=str.charAt(i-1);
            --i;
            --j;
        }else{
            if(dp[i-1][j]<dp[i][j-1]){
                j--;
            }else{
                i--;
            }
        }
    }
    return reverse(ans);
}

public static String reverse(String s){
    String ans = "";
    for(int i=s.length()-1;i>=0;i--){
        ans += s.charAt(i);
    }
    return ans;
}

}

标签： algorithmdata-structuresdynamic-programming

Answer 1

我正在提供一种替代但简单的动态编程实现，它将解决您的问题。 表示在给定字符串中的位置结束dp[i][j] = 1的大小回文。ij

示例：str = "aprabaprrbcb"那么dp[3][5] represents "aba". 由于"aba" is palindrome, dp[3][5] = 1.

我们只需要检查当前子字符串的第一个和最后一个字符是否为equal. 如果相等，则检查inner sub-string（删除当前字符串的第一个和最后一个字符后的字符串）是否为回文。由于内部子字符串的大小将是i-2并且结束于j-1，因此我们检查dp[i-2][j-1]。

现在维护 2 个变量lar_size和lar_pos最长回文的大小和该回文的最后一个索引。

import java.util.Scanner;

public class LPS { 
    public static void main(String[] args){
        Scanner sc= new Scanner(System.in);
        String str = sc.nextLine();
        sc.close();
        int n= str.length();
        int[][] dp = new int[n+1][n+1];
        int lar_size=-1;
        int lar_pos= -1;
        for(int i=0;i<=n;i++){
            dp[0][i]=1; //string of length 0 ending at position i is a palindrome
            dp[1][i]=1; //string of length 1 ending at position i is a palindrome
        }
        //
        for( int i=2;i<=n;i++){
            for( int j=i; j<=n;j++){
                if(str.charAt(j-1) == str.charAt(j-i)){
                    if(dp[i-2][j-1] == 1){
                        dp[i][j]=1;
                        if(lar_size < i){ // for lowest index palindrome
                            lar_size=i;
                            lar_pos=j;
                        }
                        
                    }

                }
            }
        }
        System.out.println(lar_size+" "+(lar_pos-lar_size+1));
        String ans="";
        for(int i=0;i<lar_size;i++){
            ans+=str.charAt(lar_pos-lar_size+1 +i);
        }
        System.out.println(ans);
    }
}