题目描述

给出两个字符串 str1 和 str2，返回同时以 str1 和 str2 作为子序列的最短字符串。如果答案不止一个，则可以返回满足条件的任意一个答案。

（如果从字符串 T 中删除一些字符（也可能不删除，并且选出的这些字符可以位于 T 中的 任意位置），可以得到字符串 S，那么 S 就是 T 的子序列）

样例

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

算法1

(动态规划) $O(n^2)$

dp[ i ][ j ] 表示 包含第一个字符串的前i个字符和第二个字符串的前j个字符的子串的最小长度

1.
dp[ i ][ j ] = min( dp[ i - 1 ][ j ], dp[ i ][ j - 1 ] ) + 1;
2.
如果 s1[ i ] == s2[ j ];
dp[ i ][ j ] = min( dp[ i ][ j ], dp[ i - 1 ][ j - 1 ] + 1 );

求其目标的字符串有两种方法

1.
直接string str[ 1010 ][ 1010 ]来求，比较简单，但是MLE

2.
进行回溯
记目标字符串为goal
分为三种情况
a.
dp[ i ][ j ] == dp[ i - 1 ][ j - 1 ] + 1;
goal += s1[ i ] || s2[ j ];

b.
dp[ i ][ j ] == dp[ i - 1 ][ j ] + 1;
goal += s1[ i ]

c.
dp[ i ][ j ] == dp[ i ][ j - 1 ] + 1;
goal += s2[ j ]

C++ 代码

//MLE代码
class Solution {

private:
    string str[ 1010 ][ 1010 ];

public:
    string shortestCommonSupersequence(string s1, string s2) {
    int n1 = s1.length();
    int n2 = s2.length();
    for( int i = 1; i <= n1; i ++ ) str[ i ][ 0 ] = str[ i - 1 ][ 0 ] + s1[ i - 1 ];
    for( int i = 1; i <= n2; i ++ ) str[ 0 ][ i ] = str[ 0 ][ i - 1 ] + s2[ i - 1 ];

    for( int i = 1; i <= n1; i ++ )
    for( int j = 1; j <= n2; j ++ )
    {
        str[ i ][ j ] = str[ i - 1 ][ j ] + s1[ i - 1 ];
        if( str[ i ][ j ].length() > str[ i ][ j - 1 ].length() + 1 )
            str[ i ][ j ] = str[ i ][ j - 1 ] + s2[ j - 1 ];
        if( s1[ i - 1 ] == s2[ j - 1 ] && str[ i ][ j ].length() > str[ i - 1 ][ j - 1 ].length() + 1 )
            str[ i ][ j ] = str[ i - 1 ][ j - 1 ] + s1[ i - 1 ];
    }
    return str[ n1 ][ n2 ];   
}
};

//AC代码
class Solution {

private:
    string goal;
    int dp[ 1010 ][ 1010 ];

public:
    string shortestCommonSupersequence(string s1, string s2) {
    int n1 = s1.length();
    int n2 = s2.length();
    for( int i = 1; i <= n1; i ++ ) dp[ i ][ 0 ] = i;
    for( int i = 1; i <= n2; i ++ ) dp[ 0 ][ i ] = i;

    for( int i = 1; i <= n1; i ++ )
    for( int j = 1; j <= n2; j ++ )
    {
        dp[ i ][ j ] = min( dp[ i - 1 ][ j ], dp[ i ][ j - 1 ] ) + 1;
        if( s1[ i - 1 ] == s2[ j - 1 ] ) 
            dp[ i ][ j ] = min( dp[ i ][ j ], dp[ i - 1 ][ j - 1 ] + 1 );
    }
    build( n1, n2, s1, s2 );
    reverse( goal.begin(), goal.end() );
    return goal;    
 }

void build( int n1, int n2, string s1, string s2 )
{
    while( n1 && n2 )
    {
        if( dp[ n1 ][ n2 ] == dp[ n1 - 1 ][ n2 ] + 1 )      goal += s1[ -- n1 ];
        else if( dp[ n1 ][ n2 ] == dp[ n1 ][ n2 - 1 ] + 1 ) goal += s2[ -- n2 ];
        else
        {
            goal += s1[ n1 - 1 ];
            n2 --;
            n1 --;
        }
    }
    while( n1 ) goal += s1[ -- n1 ];
    while( n2 ) goal += s2[ -- n2 ];
}

};