ac

给定三个字符串str1、str2 和aim,如果aim包含且仅包含来自str1和str2的所有字符，而且在aim中属于str1的字符之间保持原来在str1中的顺序属于str2的字符之间保持原来在str2中的顺序，那么称aim是str1和str2的交错组成。实现一个函数，判断aim是否是str1和str2交错组成，如果是请输出“YES”，否则输出“NO”。

import java.util.Scanner;


public class Main {

    public static Scanner sc = new Scanner(System.in);

    public static void main(String[] args) {
        String str1 = sc.next();
        String str2 = sc.next();
        String aim = sc.next();
        if(checkInclude(str1, aim) && checkInclude(str2, aim)){
            System.out.println("YES");
        }else {
            System.out.println("NO");
        }
    }

    static boolean checkInclude(String s, String aim){
        int n1 = s.length();
        int n2 = aim.length();
        if(n1 > n2){
            return false;
        }else if(n1 == n2){
            if(s.equals(aim)){
                return true;
            }
            return false;
        }else {
            if(getMaxLen(s, aim) == n1){
                return true;
            }
            return false;
        }
    }

    // 最大公共子序列
    static int getMaxLen(String s1, String s2){
        int n1 = s1.length();
        int n2 = s2.length();
        // s1
        // s2
        int[][] dp = new int[n2+1][n1+1];
        for(int i=0;i<=n1;i++){
            dp[0][i] = 0;
        }
        for(int i=0;i<=n2;i++){
            dp[i][0] = 0;
        }
        int maxLen = 0;
        for(int i=0;i<n2;i++){
            // 已经有 dp[i][0....n2]
            // 当前求出 dp[i+1][1...j+1]
            for(int j=0;j<n1;j++){
                if(s2.charAt(i) == s1.charAt(j)){
                    dp[i+1][j+1] = dp[i][j] + 1;
                }
                dp[i+1][j+1] = Math.max(dp[i+1][j+1], dp[i+1][j]);
                dp[i+1][j+1] = Math.max(dp[i+1][j+1], dp[i][j+1]);

                if(dp[i+1][j+1] > maxLen){
                    maxLen = dp[i+1][j+1];
                }
            }
        }
        return maxLen;
    }

}
/*
AB
12
1AB2

YES

2019
9102
22001199

NO
*/