题解 | #交织子序列#

import java.util.*;


public class Solution {
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     * 
     * @param s string字符串 
     * @param x string字符串 
     * @param t string字符串 
     * @return bool布尔型
     */
    public boolean isInterleave (String s, String x, String t) {
        // write code here
        return process_isInterleav(s, x, t);
    }
    private boolean process_isInterleav (String s, String x, String t) {
        if (!contain_str(s, x, t)) {
			return false;
		}
		int n = s.length();
		int m = x.length();
		boolean[][] dp = new boolean[n + 1][m + 1];
		if (s.charAt(n - 1) == t.charAt(n + m - 1)) {			
			dp[n - 1][m] = true;
		}
		if (x.charAt(m - 1) == t.charAt(n + m - 1)) {			
			dp[n][m - 1] = true;
		}
		for (int j = m - 2; j >= 0; j--) {
			dp[n][j] = x.charAt(j) == t.charAt(n + j) && dp[n][j + 1];
		}
		for (int i = n - 2; i >= 0; i--) {
			dp[i][m] = s.charAt(i) == t.charAt(i) && dp[i + 1][m];
		}
		// 动态规划的顺序
		for (int i = n - 1; i >= 0; i--) {
			for (int j = m - 1; j >= 0; j--) {
				if (s.charAt(i) == t.charAt(i + j)) {
					dp[i][j] = dp[i + 1][j];
				}
				if (x.charAt(j) == t.charAt(i + j)) {
					dp[i][j] = (dp[i][j] || dp[i][j + 1]);
				}
			}
		}
		return dp[0][0];
    }
    // ma mt mtam
    private boolean contain_str(String s, String x, String t) {
        if (s.length() + x.length() != t.length()) {
            return false;
        }
        int[] arr = new int[26];
        for (int i = 0; i < s.length(); i++) {
            arr[s.charAt(i) - 'a']++;
        }
        for (int i = 0; i < x.length(); i++) {
            arr[x.charAt(i) - 'a']++;
        }
        for (int i = 0; i < t.length(); i++) {
            arr[t.charAt(i) - 'a']--;
        }
        for (int i = 0; i < 26; i++) {
            if (arr[i] != 0) {
                return false;
            }
        }
        return true;
    }
}

import java.util.*;
 
 
public class Solution {
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     *
     * @param s string字符串
     * @param x string字符串
     * @param t string字符串
     * @return bool布尔型
     */
    public boolean isInterleave (String s, String x, String t) {
        // write code here
        if (!contain_str(s, x, t)) {
            return false;
        }
        return process(s, x, t, 0, 0);
    }
    public boolean process(String s, String x, String t, int p1, int p2) {
        if (p1 + p2 + 1 == t.length()) {
            return true;
        }
        boolean res = false;
        int p = p1 +p2;
        if (p1 < s.length() && s.charAt(p1) == t.charAt(p)) {
            res = process(s, x, t, p1 + 1, p2);
        }
        if (p2 < x.length()&&  x.charAt(p2) == t.charAt(p)) {
            res = (res || process(s,  x, t, p1, p2 + 1));
        }
        return res;
    }
    public boolean contain_str(String s, String x, String t) {
        int[] arr = new int[26];
        for (int i = 0; i <s.length(); i++) {
            arr[s.charAt(i) - 'a']++;
        }
        for (int j = 0; j <x.length(); j++) {
            arr[x.charAt(j) - 'a']++;
        }
        for (int i = 0; i <t.length(); i++) {
            arr[t.charAt(i) - 'a']--;
        }
        for (int i = 0; i < arr.length; i++) {
            if(arr[i] != 0) return false;
        }
        return true;
    }
}import java.util.*;
 
 
public class Solution {
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     *
     * @param s string字符串
     * @param x string字符串
     * @param t string字符串
     * @return bool布尔型
     */
    public boolean isInterleave (String s, String x, String t) {
        // write code here
        if (!contain_str(s, x, t)) {
            return false;
        }
        int n = s.length();
        int m = x.length();
        int len = m + n;
        // boolean[][] dp = new boolean[n +1][m + 1];
        // dp[n][m - 1] = true;
    //    dp[n - 1][m] =          true;
       // "cwm","kmz","ckmwz"
    //    for (int j = 0; j < m; j++) {
        // dp[n][j] = x.charAt(j) == t.charAt(j + n);
    //    }
    //    for (int i = 0; i < n; i++) {
        // dp[i][m] = x.charAt(i) == t.charAt(i);
    //    }
        // for (int i = n - 1; i >= 0; i--) {
            // for (int j = m - 1; j >= 0; j--) {
                // dp[i][j] = false;
                // if (s.charAt(i) == t.charAt(i + j)) {
                    // dp[i][j] = dp[i +1][j];
                // }
                // if (x.charAt(j) == t.charAt(i + j)) {
                    // dp[i][j] = (dp[i][j] || dp[i][j +1]);
                // }
            // }
        // }
        // return dp[0][0];
        return process(s, x, t, 0, 0);
    }
    public boolean process(String s, String x, String t, int p1, int p2) {
        if (p1 + p2 + 1 == t.length()) {
            return true;
        }
        boolean res = false;
        int p = p1 +p2;
        if (p1 < s.length() && s.charAt(p1) == t.charAt(p)) {
            res = process(s, x, t, p1 + 1, p2);
        }
        if (p2 < x.length()&&  x.charAt(p2) == t.charAt(p)) {
            res = (res || process(s,  x, t, p1, p2 + 1));
        }
        return res;
    }
    public boolean contain_str(String s, String x, String t) {
        int[] arr = new int[26];
        for (int i = 0; i <s.length(); i++) {
            arr[s.charAt(i) - 'a']++;
        }
        for (int j = 0; j <x.length(); j++) {
            arr[x.charAt(j) - 'a']++;
        }
        for (int i = 0; i <t.length(); i++) {
            arr[t.charAt(i) - 'a']--;
        }
        for (int i = 0; i < arr.length; i++) {
            if(arr[i] != 0) return false;
        }
        return true;
    }
}

题目：

• 牛牛和朋友正在使用一种新型消息传输系统。在这个系统中，有一个特殊的编码方式，它允许将两个字符串 s 和 x 交织在一起，形成一个新的字符串 t，要求保持它们的字符顺序不变。如果字符串 t 既包含字符串 s 的子序列，也包含字符串 x 的子序列，包含部分不重复，且刚好由这两个子序列组成，那么 t 就称为 s 和 x 的交织子序列。
• 给定三个字符串 s, x, t，请判断 t 是否是 s 和 x 的交织子序列。

思路：

• dfs：采用深度优先遍历，递归函数的意义是从s和x字符串的0，0位置是否可以到达它们各自的末尾
• 遍历过程只有当它们在t字符串的相应位置（i+j）和它们自身匹配才可以向后移动
• 递归转动态规划，将dp[i][j]定义为递归函数的含义，然后初始化dp函数的最后一行和最后一列
• 初始化行列的时候根据递归函数的base case进行初始化， 就是当可以到达i+j+1位置且对应匹配时为true，否则为false