求最長迴文子序列長度問題
求最長迴文子序列長度問題
作者：Grey
原文地址：
題目描述
給你一個字符串 s ，找出其中最長的迴文子序列，並返回該序列的長度。題目鏈接見:LeetCode 516. Longest Palindromic Subsequence
暴力解
定義遞歸函數
int process(int i, int j, char[] str)
遞歸含義是：str 這個字符串從 i 到 j，最長迴文子序列長度是多少。
主函數只需要調用
return process(0, str.length - 1, str);
即為要求的答案。
接下來看遞歸函數的實現
首先是 base case，顯然有如下兩個結論：
結論1：當i == j的時候，說明只有一個字符，最長迴文子序列長度就是 1；
結論2：當i == j - 1的時候，如果str[i] == str[j]，則最長迴文子序列的長度就是 2， 否則就是 1；
接下來就是普遍情況：
要求i……j之間的最長迴文子序列的長度，有如下三種情況
情況1，不考慮 i 位置的字符，則i……j之間的最長迴文子序列的長度就是i+1……j之間的最長迴文子序列長度。
情況2，不考慮 j 位置的字符，則i……j之間的最長迴文子序列的長度就是i……j-1之間的最長迴文子序列的長度。
情況3，當str[i] == str[j]的時候，i……j之間的最長迴文子序列的長度就是i+1……j-1之間的最長迴文子序列的長度加 2。
以上三種情況求最大值，就是i……j之間的最長迴文子序列的長度。
暴力解法的完整代碼如下
class Solution {
public static int longestPalindromeSubseq(String s) {
if (s == null || s.length() < 1) {
return 0;
}
char[] str = s.toCharArray();
return process(0, str.length - 1, str);
}
// i...j的最長迴文子序列是多少
public static int process(int i, int j, char[] str) {
if (i == j) {
return 1;
}
if (i == j - 1) {
return str[i] == str[j] ? 2 : 1;
}
int p1 = process(i + 1, j, str);
int p2 = process(i, j - 1, str);
int p3 = (str[i] == str[j] ? 2 : 0) + process(i + 1, j - 1, str);
return Math.max(p1, Math.max(p2, p3));
}
}
LeetCode 上這個解法會直接超時
動態規劃
通過暴力遞歸方法
public static int process(int i, int j, char[] str) {
...
int p1 = process(i + 1, j, str);
int p2 = process(i, j - 1, str);
... process(i + 1, j - 1, str);
....
}
我們可以得到一個結論，原問題是一個二維數組規模的問題，使用一個二維數組就可以把整個遞歸中的解保存下來，二維數組定義如下
int[][] dp = new int[s.length()][s.length()];
dp[i][j]就是遞歸函數process(i,j,str)的含義，即：str 這個字符串從 i 到 j，最長迴文子序列長度是多少。
且任何一個(i,j)位置依賴三個位置的值，即：(i,j-1),(i+1,j),(i+1,j-1)
二維數組的對角線位置的值都是 1，因為對角線i == j，只有一個字符，最大迴文子序列就是 1，
接下來按照遞歸含義依次填好每個二維數組格子的值，說明見注釋
for (int i = 0; i < s.length(); i++) {
// 對角線都是1
dp[i][i] = 1;
if (i != s.length() - 1) {
// 對角線上一條線 不是 1 就是 2
dp[i][i + 1] = str[i] == str[i + 1] ? 2 : 1;
}
}
// 普遍位置
for (int index = 2; index < s.length(); index++) {
int i = 0;
int j = index;
while (j < s.length()) {
int p1 = dp[i + 1][j];
int p2 = dp[i][j - 1];
int p3 = (str[i] == str[j] ? 2 : 0) + dp[i + 1][j - 1];
dp[i][j] = Math.max(p1, Math.max(p2, p3));
i++;
j++;
}
}
// 返回dp[0][s.length() - 1]： 即 整個字符串的最長迴文子序列的長度
return dp[0][s.length() - 1];
完整代碼如下
class Solution {
public static int longestPalindromeSubseq(String s) {
if (s == null || s.length() < 1) {
return 0;
}
char[] str = s.toCharArray();
int[][] dp = new int[s.length()][s.length()];
for (int i = 0; i < s.length(); i++) {
dp[i][i] = 1;
if (i != s.length() - 1) {
dp[i][i + 1] = str[i] == str[i + 1] ? 2 : 1;
}
}
for (int index = 2; index < s.length(); index++) {
int i = 0;
int j = index;
while (j < s.length()) {
int p1 = dp[i + 1][j];
int p2 = dp[i][j - 1];
int p3 = (str[i] == str[j] ? 2 : 0) + dp[i + 1][j - 1];
dp[i][j] = Math.max(p1, Math.max(p2, p3));
i++;
j++;
}
}
return dp[0][s.length() - 1];
}
}
使用最大公共子序列來解
還有更多的思路可以解這個題目，比如：一個字符串和它的逆序串的最大公共子序列就是這個串的最長迴文子序列，不贅述，直接看代碼
class Solution {
public int longestPalindromeSubseq(String s) {
char[] str1 = s.toCharArray();
int n = str1.length;
char[] str2 = new char[n];
for (char str : str1) {
str2[--n] = str;
}
return longestCommonSubsequence2(str1, str2);
}
// 最長公共子序列
public int longestCommonSubsequence2(char[] str1, char[] str2) {
if ((null == str1 || str1.length == 0) || str2 == null || str2.length == 0) {
return 0;
}
int m = str1.length;
int n = str2.length;
int[][] dp = new int[m][n];
dp[0][0] = str1[0] == str2[0] ? 1 : 0;
for (int i = 1; i < n; i++) {
dp[0][i] = str1[0] == str2[i] ? 1 : dp[0][i - 1];
}
for (int i = 1; i < m; i++) {
dp[i][0] = str1[i] == str2[0] ? 1 : dp[i - 1][0];
}
for (int i = 1; i < m; i++) {
for (int j = 1; j < n; j++) {
dp[i][j] = Math.max(dp[i - 1][j], dp[i][j - 1]);
if (str1[i] == str2[j]) {
dp[i][j] = Math.max(dp[i][j], dp[i - 1][j - 1] + 1);
} else {
dp[i][j] = Math.max(dp[i][j], dp[i - 1][j - 1]);
}
}
}
return dp[m - 1][n - 1];
}
}
其中int longestCommonSubsequence2(char[] str1, char[] str2)方法就是求兩個字符串的最長公共子序列的動態規劃解法。
