[dynamic planning] leetcode1092 Shortest common supersequence

1092. The shortest common supersequence

  Given string a,b, seek a,b The shortest common supersequence of , namely a,b It is also a subsequence of this sequence and this sequence is the shortest .

The problem of converting bit editing distance

【 Dynamic programming 】 Section dp： Edit distance _ Twilight _ Blog years -CSDN Blog

The problem can be translated into ：

Yes a Add operation , Make the added a contain b, Find the minimum number of additions .

  explain ：

If you want to a[i] After adding a character, do a contain b, Then we must make a[ 1 ~ i ] contain b[ 1~ j-1 ], namely under these circumstances   dp[ i ] [ j ] = dp[ i ][ j - 1 ] + 1 .

If in a[i] You can do this without adding characters a contain b, So when a[ i ] ! =b[ j ] when , hold a[i] After removal a Can still contain b[j], So in this case ,dp[ i ][ j ] = dp[ i-1 ][ j ]

When a[ i ] = = b [ j ]  when , Sure no need  a[ i ] Take a match b[ j ],dp[ i ][ j ]=dp[ i -1 ][ j ], It can also be used. a [ i ] To match

b[ j ],dp[ i ][ j ]=dp[ i-1 ][ j- 1]

？ use for Output the result in reverse order .

class Solution {
public:
    string shortestCommonSupersequence(string a, string b) {
        int n = a.size(), m = b.size(), INF = 1e8;
        vector<vector<int>> f(n + 1, vector<int>(m + 1, INF));
        for (int i = 0; i <= n; i ++ ) f[i][0] = 0;
        for (int i = 1; i <= m; i ++ ) f[0][i] = i;

        for (int i = 1; i <= n; i ++ )
            for (int j = 1; j <= m; j ++ ) {
                f[i][j] = min(f[i][j - 1] + 1, f[i - 1][j]);
                if (a[i - 1] == b[j - 1])
                    f[i][j] = min(f[i][j], f[i - 1][j - 1]);
            }

        string res;
        for (int i = n, j = m; i >= 0;) {
            if (!i || !j || a[i - 1] != b[j - 1]) {
                if (j && f[i][j] == f[i][j - 1] + 1) {
                    res += b[ -- j];
                } else {
                    if (i) res += a[ -- i];
                    else i -- ;
                }
            } else {
                if (f[i][j] == f[i][j - 1] + 1) {
                    res += b[ -- j];
                } else if (f[i][j] == f[i - 1][j]) {
                    res += a[ -- i];
                } else {
                    res += a[ -- i];
                    j -- ;
                }
            }
        }

        reverse(res.begin(), res.end());
        return res;
    }
};