当前位置：首页 > news >正文

给定一个字符串str，求最长回文子序列长度。

news 来源：原创 2023/3/29 15:53:13

问题描述：

思想：

思想一：

根据回文串的性质，我们可以生成一个新的字符串，新字符串的顺序是原来字符串的倒序。本题可以转化为两个字符串求最长的公共子序列。

使用动态规划的思想。定义二维数组dp，行表示原本的字符串str1的字符，列表示翻转后字符串str2的每一个字符。二维数组dp[i][j]的含义是：字符串str1从下标0~i和字符串str2从下标0~j的最长公共子序列有几个字符。

最左上角dp[0][0]、第一列dp[i][0]、第一行dp[0][j]很容易填写。

对于普遍位置dp[i][j]分为下面几种情况：

1>str1的第i个字符不在子序列中，dp[i][j]=dp[i-1][j]

2>str2的第j个字符不在子序列中，dp[i][j]=dp[i][j-1]

3>str1的第i个字符和str2的第j个字符都不在子序列中，dp[i][j]=dp[i-1][j-1]

4>str1的第i个字符和str2的第j个字符都在子序列中，也就是满足天剑str1[i]==str2[j],dp[i][j]=dp[i-1][j-1]+1

最后再取这四种情况的最大值保存在dp[i][j]中。

由上面推理我们知道dp[i][j]={dp[i-1][j],dp[i][j-1],dp[i-1][j-1],dp[i-1][j-1]+1}。我们可以得知dp[i-1][j]>dp[i-1][j-1] 和dp[i][j-1]>dp[i-1][j-1]的，所以他情况3>我们就可以省略不写。

思想二：

同样使用动态规划的思想。定义二维数组dp，行列分别表示字符串str的字符。dp[i][j]表示的含义：字符串str从从下标i~j最长回文子序列有几个字符。

根据性质二维数组的左下部分不需要填写，并且左上到右下的对角线和对角线上衣对角线很容易填写出来。、

对于普遍位置的dp[i][j]，可以分为下面几种情况：

1>字符串str的第i位置不在最后的回文子序列中，dp[i][j]=dp[i+1][j]

2>字符串str的第j位置不在最后的回文子序列中，dp[i][j]=dp[i][j-1]

3>字符串str的第i和j位置不在最后的回文子序列中，dp[i][j]=dp[i+1][j-1]

4>字符串str的第i和j位置在最后的回文子序列中，也就是满足条件str[i] == str[j]时，dp[i][j]=dp[i+1][j-1]+2

最后再取这四种情况的最大值保存在dp[i][j]中。

由上面推理我们知道dp[i][j]={dp[i+1][j],dp[i][j-1],dp[i+1][j-1],dp[i+1][j-1]+2}。我们可以得知dp[i+1][j-1]>dp[i+1][j] 和dp[i][j-1]>dp[i+1][j-1]的，所以他情况3>我们就可以省略不写。

代码

思想一代码：

    public static int maxLen1(String str) {if (str == null || str.length() == 0) {return 0;}char[] str1 = str.toCharArray();char[] str2 = reverse(str1);return lcse(str1, str2);}public static char[] reverse(char[] str) {char[] reverse = new char[str.length];for (int i = 0; i < reverse.length; i++) {reverse[i] = str[str.length - 1 - i];}return reverse;}public static int lcse(char[] str1, char[] str2) {int[][] dp = new int[str1.length][str2.length];dp[0][0] = str1[0] == str2[0] ? 1 : 0;for (int i = 1; i < str1.length; i++) {dp[i][0] = Math.max(dp[i - 1][0], str1[i] == str2[0] ? 1 : 0);}for (int j = 1; j < str2.length; j++) {dp[0][j] = Math.max(dp[0][j - 1], str1[0] == str2[j] ? 1 : 0);}for (int i = 1; i < str1.length; i++) {for (int j = 1; j < str2.length; 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);}}}return dp[str1.length - 1][str2.length - 1];}

思想二代码：

    public static int maxLen2(String s) {if (s == null || s.length() == 0) {return 0;}char[] str = s.toCharArray();int[][] dp = new int[str.length][str.length];for (int i = 0; i < str.length; i++) {dp[i][i] = 1;}for (int i = 0; i < str.length - 1; i++) {dp[i][i + 1] = str[i] == str[i + 1] ? 2 : 1;}for (int i = str.length - 2; i >= 0; i--) {for (int j = i + 2; j < str.length; j++) {dp[i][j] = Math.max(dp[i][j - 1], dp[i + 1][j]);if (str[i] == str[j]) {dp[i][j] = Math.max(dp[i + 1][j - 1] + 2, dp[i][j]);}}}return dp[0][str.length - 1];}public static void main(String[] args) {String test = "A1BC2D33FG2H1I";System.out.println(maxLen1(test));System.out.println(maxLen2(test));}

问题描述：

思想：

代码

相关文章：