leetcode1092. 最短公共超序列(java-动态规划)

题目描述

难度 - 困难
leetcode1092. 最短公共超序列

给你两个字符串 str1 和 str2，返回同时以 str1 和 str2 作为 子序列 的最短字符串。如果答案不止一个，则可以返回满足条件的 任意一个 答案。
如果从字符串 t 中删除一些字符（也可能不删除），可以得到字符串 s ，那么 s 就是 t 的一个子序列。

示例 1：
输入：str1 = “abac”, str2 = “cab”
输出：“cabac”
解释：
str1 = “abac” 是 “cabac” 的一个子串，因为我们可以删去 “cabac” 的第一个 "c"得到 “abac”。
str2 = “cab” 是 “cabac” 的一个子串，因为我们可以删去 “cabac” 末尾的 “ac” 得到 “cab”。
最终我们给出的答案是满足上述属性的最短字符串。

示例 2：
输入：str1 = “aaaaaaaa”, str2 = “aaaaaaaa”
输出：“aaaaaaaa”

提示：
1 <= str1.length, str2.length <= 1000
str1 和 str2 都由小写英文字母组成。

动态规划

为了方便，我们令 str1 为 s1，str2 为 s2，并将两者长度记为 n 和 m。
容易想到最终的方案必然是由三部分组成：两字符串的公共子序列（且必然是最长公共子序列）+ 两者特有的字符部分。
基于此，我们可以先使用对两者求 LCS，并在求具体方案时遵循：属于最长公共子序列的字符只添加一次，而特有于 s1 或 s2 的字符则独自添加一次。

求解 LCS 部分我们定义 f[i][j]代表考虑s1 的前i 个字符、考虑s2 的前j 的字符，形成的最长公共子序列长度（为了方便，令下标从1开始）。
当有了「状态定义」之后，基本上「转移方程」就是呼之欲出：

• s1[i]==s2[j] : f[i][j]=f[i−1][j−1]+1。代表必然使用 s1[i] 与 s2[j] 时 LCS 的长度。
• s1[i]!=s2[j] : f[i][j]=max(f[i−1][j],f[i][j−1])。代表必然不使用 s1[i]（但可能使用s2[j]）时 和 必然不使用 s2[j]（但可能使用s1[i]）时 LCS 的长度。

当预处理出动规数组 f 之后，我们使用「双指针」和「通用 DP 求具体方案」的做法进行构造：使用 i 变量指向 s1 的尾部（即起始有 i=n），使用 j 变量指向 s2 的尾部（即起始有 j=m），根据 i 和 j 当前所在位置以及 f[i][j]从何值转移而来：

1. 若 i 或 j 其一走完（i = 0 或 j = 0），将剩余字符追加到答案中.
2. 当 f[i][j]=f[i−1][j−1]+1 且 s1[i]=s2[j]时（可简化为 s1[i]=s2[j] 判断），此时 i 指向的字符和 j 指向的字符为相同，且为 LCS 中的字符，将其追加到具体方案，并让 i 和 j 同时后移；
3. 当 f[i][j]=f[i−1][j]，将 s1[i] 追加到答案中，令 i 后移；
4. 当 f[i][j]=f[i][j−1]，将 s2[j] 追加到答案中，令 j 后移。

当条件 3 和 4 同时满足时，由于只需要输出任一具体方案，我们任取其一即可。
最后，由于我们是从后往前进行构造，在返回时需要再进行一次翻转。

代码演示

class Solution {
    public String shortestCommonSupersequence(String str1, String str2) {
       int n = str1.length();
       int m = str2.length();
       int[][]f = new int[n + 10][m + 10];
       str1 = " " + str1;
       str2 = " " + str2;
       char[]s1 = str1.toCharArray(); 
       char[]s2 = str2.toCharArray();
       for(int i = 1;i <= n;i++){
           for(int j = 1;j <= m;j++){
               if(s1[i] == s2[j]){
                   f[i][j] = f[i - 1][j - 1] + 1;
               }else{
                   f[i][j] = Math.max(f[i - 1][j], f[i][j - 1]);
               }
           }
       }
       StringBuilder sb = new StringBuilder(); 
       int i = n,j = m;
       while(i > 0 || j > 0){
           if(i == 0){
               sb.append(s2[j--]);
           }else if(j == 0){
               sb.append(s1[i--]);
           }else {
               if(s1[i] == s2[j]){
                   sb.append(s1[i]);
                   i--;
                   j--;
               }else if(f[i][j] == f[i - 1][j]){
                   sb.append(s1[i--]);
               }else{
                   sb.append(s2[j--]);
               }
           }

       }
       return sb.reverse().toString();
    }
}
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
31
32
33
34
35
36
37
38
39
40
41