使用lcs的最长回文子串

Question

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