题目

给你两个字符串 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 都由小写英文字母组成。

思路

toCharArray

解法

class Solution {
    public String shortestCommonSupersequence(String str1, String str2) {
        char[] c1=str1.toCharArray();
        char[] c2=str2.toCharArray();
        int[][] dp=new int[c1.length+1][c2.length+1];
        for(int i=1;i<c1.length+1;++i){
            for(int j=1;j<c2.length+1;++j){
                if(c1[i-1]==c2[j-1])
                    dp[i][j]=dp[i-1][j-1]+1;
                else
                    dp[i][j]=Math.max(dp[i-1][j],dp[i][j-1]);
            }
        }

        int m=c1.length,n=c2.length;
        StringBuilder sb=new StringBuilder();
        while(m>0||n>0){
            char temp=' ';
            if(m==0){
                temp=c2[n-1];
                n--;
            }
            else if(n==0){
                temp=c1[m-1];
                m--;
            }
            else{
                if(c1[m-1]==c2[n-1]){
                    temp=c1[m-1];
                    m--;
                    n--;
                }
                else if(dp[m][n]==dp[m-1][n]){
                    temp=c1[m-1];
                    m--;
                }
                else if(dp[m][n]==dp[m][n-1]){
                    temp=c2[n-1];
                    n--;
                }
            }
            sb.append(temp);
        }
        return sb.reverse().toString();
    }
}

总结

• 分析出几种情况，然后分别对各个情况实现