题解 | #交织子序列# java
交织子序列
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) { // write code here int n = s.length(); int m = x.length(); int 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]; } }
编程语言是Java。
该题考察的知识点是动态规划。
代码的文字解释:
isInterleave
方法接受三个字符串参数s
、x
和t
,并返回一个布尔值。- 首先获取字符串
s
、x
和t
的长度分别为n
、m
和k
。 - 如果
s
和x
合并起来的长度不等于t
的长度k
,则直接返回false。 - 创建一个布尔数组
f
,长度为m+1
,用于记录状态转移的结果。 - 初始化
f[0]
为true,表示空字符串可以由空字符串组成。 - 使用两层循环遍历字符串
s
和x
的每个位置:根据当前位置计算t中对应位置的索引p。如果s的前缀可以与t中对应位置匹配,则将f[j]更新为s.charAt(i - 1) == t.charAt(p),即取决于之前位置的结果和当前字符是否匹配。如果x的前缀可以与t中对应位置匹配,则将f[j]更新为之前位置的结果f[j - 1]与当前字符是否匹配x.charAt(j - 1) == t.charAt(p)的逻辑或结果。 - 循环结束后,返回
f[m]
,即表示整个字符串t
是否由字符串s
和x
交错组成的结果。