题解 | #交织子序列#
交织子序列
https://www.nowcoder.com/practice/3885d44d77f34f1c89dc05ac40207f5d
- 题目考察的知识点 :
- 题目解答方法的文字分析:
- 定义一个二维数组dp,其中dp[i][j]表示字符串 s 的前i个字符串s的前j个字符是否能够交织成字符串t的前i+j个字符的子序列。
- 对于字符串s和x中的每个字符,我们都有两种选择:
- 将它加入当前组成的子序列中;
- 将它不加入当前组成的子序列中;
- 得出状态转移方程
- 本题解析所用的编程语言: Python
- 完整且正确的编程代码
# # 代码中的类名、方法名、参数名已经指定,请勿修改,直接返回方法规定的值即可 # # # @param s string字符串 # @param x string字符串 # @param t string字符串 # @return bool布尔型 # class Solution: def isInterleave(self, s: str, x: str, t: str) -> bool: m, n = len(s), len(x) if m + n != len(t): return False # dp[i][j] 表示 s 的前 i 个字符和 x 的前 j 个字符能否构成 t 的前 i+j 个字符的子序列 dp = [[False] * (n + 1) for _ in range(m + 1)] dp[0][0] = True for i in range(1, m + 1): dp[i][0] = dp[i - 1][0] and s[i - 1] == t[i - 1] for j in range(1, n + 1): dp[0][j] = dp[0][j - 1] and x[j - 1] == t[j - 1] for i in range(1, m + 1): for j in range(1, n + 1): dp[i][j] = (dp[i - 1][j] and s[i - 1] == t[i + j - 1]) or ( dp[i][j - 1] and x[j - 1] == t[i + j - 1] ) return dp[m][n]
牛客高频top202题解系列 文章被收录于专栏
记录刷牛客高频202题的解法思路