题解 | #交织子序列#
交织子序列
https://www.nowcoder.com/practice/3885d44d77f34f1c89dc05ac40207f5d
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) { int m = s.length(); int n = x.length(); int len = t.length(); if (m + n != len) { return false; } boolean[][] dp = new boolean[m + 1][n + 1]; dp[0][0] = true; // 初始化 dp 数组的第一行和第一列 for (int i = 1; i <= m; ++i) { dp[i][0] = (s.charAt(i - 1) == t.charAt(i - 1)) && dp[i - 1][0]; } for (int j = 1; j <= n; ++j) { dp[0][j] = (x.charAt(j - 1) == t.charAt(j - 1)) && dp[0][j - 1]; } // 动态规划计算 dp 数组 for (int i = 1; i <= m; ++i) { for (int j = 1; j <= n; ++j) { if ((s.charAt(i - 1) == t.charAt(i + j - 1) && dp[i - 1][j]) || (x.charAt(j - 1) == t.charAt(i + j - 1) && dp[i][j - 1])) { dp[i][j] = true; } } } return dp[m][n]; } // 方法二: // int n = s.length(), m = x.length(), k = t.length(); // if (n + m != k) { // return false; // } // boolean[] f = new boolean[m + 1]; // f[0] = true; // for (int i = 0; i <= n; ++i) { // for (int j = 0; j <= m; ++j) { // int p = i + j - 1; // if (i > 0) { // f[j] &= (s.charAt(i - 1) == t.charAt(p)); // } // if (j > 0) { // f[j] |= (f[j - 1] && x.charAt(j - 1) == t.charAt(p)); // } // } // } // return f[m]; // } }
知识点:
动态规划
解题分析:
- 定义一个大小为m+1的布尔型数组f,表示字符串x的前j个字符和字符串s的前i个字符是否能够交错组成字符串t的前i+j个字符。
- 初始化数组f的第一个元素为true,表示空字符串可以由空字符串组成。
- 使用两层循环遍历数组f,其中i表示字符串s的前i个字符,j表示字符串x的前j个字符:计算当前位置在字符串t中的索引p = i + j - 1。如果i大于0,则判断s的第i个字符是否与t的第p个字符相等,并更新f[j]的值为f[j]与(s.charAt(i-1) == t.charAt(p))的逻辑与结果。如果j大于0,则判断x的第j个字符是否与t的第p个字符相等,并更新f[j]的值为f[j]或(f[j-1] && x.charAt(j-1) == t.charAt(p))的逻辑或结果。
- 返回f[m]的值,即字符串x的全部字符和字符串s的全部字符是否能够交错组成字符串t的全部字符。
编程语言:
java