太原网站快速排名提升,做电视直播网站,wordpress 建多站,深圳市有方科技有限公司目录
97. 交错字符串 97. 交错字符串 题意#xff1a; 给定三个字符串 s1、s2、s3#xff0c;请你帮忙验证 s3 是否是由 s1 和 s2 交错 组成的。 两个字符串 s 和 t 交错 的定义与过程如下#xff0c;其中每个字符串都会被分割成若干 非空 子字符串#xff1a; s s1 s2 …目录
97. 交错字符串 97. 交错字符串 题意 给定三个字符串 s1、s2、s3请你帮忙验证 s3 是否是由 s1 和 s2 交错 组成的。 两个字符串 s 和 t 交错 的定义与过程如下其中每个字符串都会被分割成若干 非空 子字符串 s s1 s2 ... snt t1 t2 ... tm|n - m| 1交错 是 s1 t1 s2 t2 s3 t3 ... 或者 t1 s1 t2 s2 t3 s3 ... 注意a b 意味着字符串 a 和 b 连接。 【输入样例】s1 aabcc, s2 dbbca, s3 aadbbcbcac 【输出样例】true 解题思路 1. 如果s1的长度s2的长度不等于s3的长度直接返回false否则 2. 定义动态数组dp[i][j]表示s1的前i个元素和s2的第j个元素能够否交错组成s3的前ij个元素 3. dp[i][j]能否为true取决于dp[i-1][j]是否为trues1[i]s3[ij],同理dp[i][j]也取决于dp[i][j-1]s2[j]s3[ij] 4. dp的边界条件应该是dp[0][0]true即s1和s2的前0个元素可以构成s3的前0个元素都为空。 class Solution {public boolean isInterleave(String s1, String s2, String s3) {//先判断长度int len1 s1.length();int len2 s2.length();int len3 s3.length();if(len3 ! len1len2){return false;}boolean[][] dp new boolean[len11][len21];dp[0][0] true;for(int i 0; i len1; i){for(int j 0; j len2; j){int p i j - 1;if(i 0){dp[i][j] dp[i][j] || (dp[i-1][j] s1.charAt(i-1) s3.charAt(p));}if(j 0){dp[i][j] dp[i][j] || (dp[i][j-1] s2.charAt(j-1) s3.charAt(p));}}}return dp[len1][len2];}
} 时间 击败了66.74% 内存 击败了25.11%
