1771.由子序列构造的最长回文串的长度

发表于： 分类于：
字数： 1310 阅读：≈ 3分钟

📎 1771.由子序列构造的最长回文串的长度

给你两个字符串 word1 和 word2 ，请你按下述方法构造一个字符串：

  • 从 word1 中选出某个 非空 子序列 subsequence1 。
  • 从 word2 中选出某个 非空 子序列 subsequence2 。
  • 连接两个子序列 subsequence1 + subsequence2 ，得到字符串。

返回可按上述方法构造的最长 回文串 的 长度 。如果无法构造回文串，返回 0 。

字符串 s 的一个 子序列 是通过从 s 中删除一些（也可能不删除）字符而不更改其余字符的顺序生成的字符串。

回文串 是正着读和反着读结果一致的字符串。

思路

基本思想

本题看完之后第一思想是将两个字符串拼接在一起形成一个字符串，这样就可以利用 516.最长回文子序列 的解法直接进行求解，但是按照这种方式求解之后，发现只能解决一部分问题，例如word1=”bcb“,word2="a"时，最终求出来的结果是”bcb“而返回3，而不是返回0，因为word2中没有提供任何字符串。并且如果出现word1 = "aa", word2 = "bb"时，会返回1并不会返回0，这是因为 516.最长回文子序列 的解法认为一个字符也是一个回文串，但是本题中不会

知道这两个题的差异之后，我们就要想办法在 516.最长回文子序列 的解法基础上剔除这些不符合条件的回文串，然后在剩下的回文串中找到一个最长的回文子序列，先给出 516.最长回文子序列 的解法的代码：

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25

class Solution {
    public int longestPalindromeSubseq(String s) {
        char[] arr=s.toCharArray();
        //初始化dp数组
        int[][] dp=new int[s.length()][s.length()];
        int res=1;
        //开始进行动态规划
        for(int i=arr.length-1;i>=0;--i){
            for(int j=i;j<arr.length;++j){
                //两边范围相等时可以更新
                if(arr[i]==arr[j]){
                    if(i==j||i+1==j){
                        dp[i][j]=j-i+1;
                    }else{
                        dp[i][j]=dp[i+1][j-1]+2;
                    }
                }else{
                    dp[i][j]=Math.max(dp[i+1][j],dp[i][j-1]);
                }
                res=Math.max(res,dp[i][j]);
            }
        }
        return res;
    }
}

根据上面的代码进行分析，主要的问题出现在更新res和res的初值上，在更新的过程中，i和j分别代表当前这个子序列的左边界和右边界，所以只有当左边界在word1中，右边界在word2中时才能更新res，并且res的初值不能是1而是0，因为题目要求word1和word2中都必须选择至少一个字符，所以res要么是大于1的数，要么就是0，不可能是1

核心就是在 516.最长回文子序列 的解法基础上进一步增加筛选条件进行筛选

执行流程

  1. 将word1和word2合并并转换成字符数组
  2. 初始化一个二维dp数组，其中dp[i][j]代表范围i~j之间的最长回文子序列的长度
  3. 按照 516.最长回文子序列 的解法更新dp数组
  4. 改变res的初始和更新方式，只有当回文串的左边界在word1中，右边界在word2中时才更新
  5. 更新完毕之后返回结果

代码

根据以上分析，得出以下代码：

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30

class Solution {
    //类似于求出一个最长的子序列
    public int longestPalindrome(String word1, String word2) {
         char[] arr=(word1+word2).toCharArray();
        //初始化dp数组
        int[][] dp=new int[arr.length][arr.length];
        //初值必须是0
        int res=0;
        //开始进行动态规划
        for(int i=arr.length-1;i>=0;--i){
            for(int j=i;j<arr.length;++j){
                //两边范围相等时可以更新
                if(arr[i]==arr[j]){
                    if(i==j||i+1==j){
                        dp[i][j]=j-i+1;
                    }else{
                        dp[i][j]=dp[i+1][j-1]+2;
                    }
                    //只有word1和word2都涉及到时才能更新
                    if(i<word1.length()&&j>=word1.length()){
                        res=Math.max(res,dp[i][j]);
                    }
                }else{
                    dp[i][j]=Math.max(dp[i+1][j],dp[i][j-1]);
                }
            }
        }
        return res;
    }
}

总结

主要是要有 516.最长回文子序列 的基础，然后看到这个题想到 516.最长回文子序列 的解法之后，出现一些问题，主要是一些不合法的回文串被统计了，而且res的初值设置的不对，解决这两个问题之后，问题迎刃而解，相当于在 516.最长回文子序列 的解法上进行了进一步的筛选，只有左边界在word1中右边界在word2中的回文串才需要被统计