palindrome - 使用lcs的最长回文子串？

Question

我正在解决这个问题 longest palindromic substring leetcode 上的问题，我遵循动态编程方法，创建了一个 n*n bool 表(我猜这也是此问题的标准解决方案)并成功解决了它，但我只是想知道这个问题是否可以使用我们的技术来解决用于找出最长公共(public)子序列或更准确地说，只是想知道 LCS 问题是否是该问题的父问题，就像最长回文子序列的情况一样，可以通过 LCS 轻松解决，将另一个字符串作为原始字符串的反转。
我搜索了网页，但没有找到任何使用 LCS 技术的解决方案，这就是为什么想在这里问它的原因。如果可以使用 lcs 技术解决，那么请提供方法或一些很好的理由说明为什么无法使用 LCS 解决。

Answer 1

我实际上以您想要的确切方式解决了这个确切的问题!我们可以在 LCS 方法中使用单个数组来执行此操作，但这样做的开销是您必须手动检查每个组合是否是回文。这种方式的解决方法见下文。这在 LC 上也被接受。

    public String longestPalindrome(String s) {
        int maxlen = 1;
        int len = s.length();
        String[] dp = new String[len];
        dp[0] = s.substring(0,1);
        for (int i = 1; i < len; i++) {
            dp[i] = dp[i-1];
            for (int j = 0; i - j >= maxlen; j++) {
                if (s.charAt(j) != s.charAt(i)) continue;
                if (isPal(s.substring(j, i + 1))) {
                    dp[i] = s.substring(j, i + 1);
                    maxlen = i - j;
                    break;
                }
            }
        }
        return dp[len-1];
    }
    
    public boolean isPal(String s) {
        for (int i = 0; i < s.length()/2; i++) {
            if (s.charAt(i) != s.charAt(s.length()-1-i)) return false;
        }
        return true;
    }