使用lcs的最长回文子串？

Question

我是在leetcode上解决这个longest palindromic substring问题的，我遵循了动态编程的方法，创建了一个n*n布尔表(我猜这也是这个问题的标准解决方案)，并成功地解决了它，但我只是想知道这个问题是否可以用我们用来找出最长公共子序列的技术来解决，或者更准确地说，只想知道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;
    }