小网站关键词搜什么,佛山制作手机网站,莱芜金点子广告手机版,做网站的html代码格式题目链接#xff1a;力扣#xff08;LeetCode#xff09;官网 - 全球极客挚爱的技术成长平台 解题思路#xff1a;动态规划。
如果s1.length()s2.length ! s3.length()#xff0c;直接返回false#xff0c;否则使用动态规划求解。定义状态#xff1a;dp[i][i]#xff…题目链接力扣LeetCode官网 - 全球极客挚爱的技术成长平台 解题思路动态规划。
如果s1.length()s2.length ! s3.length()直接返回false否则使用动态规划求解。定义状态dp[i][i]表示s3的前ij个字符是否由 s1的前 i 和字符和s2的前j个字符交错组成初始状态dp[0][0]显然当s1s2s3都为空时dp[0][0]true状态转移对于dp[i][j]判断 s 的第 ij 个字符即 s[i j -1]是由 s1[i-1] 匹配还是 s2[j-1] 匹配(索引从开始) 如果 i 0如果由s1[i-1]匹配即 s3[i j -1] s1[ i-1] 并且 dp[i-1][j] true时dp[i][j] true如果 j 0如果由s2[j-1]匹配即 s3[i j -1] s2[ j-1] 并且 dp[i][j-1] true时dp[i][j] true因为可以连续使用s1中的字符进行匹配也可以连续使用s2中的字符进行匹配索引对于 dp[i][j]的求解需要从0开始从前往后进行遍历只要有一个符合dp[i][j] true
AC代码
class Solution {public static boolean isInterleave(String s1, String s2, String s3) {if (s1.length() s2.length() ! s3.length()) {return false;}if (s1.length() 0 || s2.length() 0) {return s3.equals(s1) || s3.equals(s2);}boolean[][] dp new boolean[s1.length() 1][s2.length() 1];dp[0][0]true;for (int i 0; i s1.length(); i) {for (int j 0; j s2.length(); j) {if (i 0) {dp[i][j] | dp[i - 1][j] s1.charAt(i-1) s3.charAt(i j - 1);}if (j 0) {dp[i][j] | dp[i][j - 1] s2.charAt(j-1) s3.charAt(i j - 1);}}}return dp[s1.length()][s2.length()];}
} 上述空间复杂度为O(mn)可以进行空间优化 求解dp[i][j]时会使用到 dp[i-1][j]和 dp[i][j-1]即状态dp[i][j]只与dp[i-1][j] 和 dp[i][j-1]有关如下图所示 可以使用一维数组进行空间优化对于 dp[i][j]的更新是从上往下从左往右进行更新的最终需要的结果右下角的值所以可以使用一维数组 dp[i]进行保存每一行的结果
初始时dp[i]保存第一行每一列的结果求解第二行时在更新前dp[i]就是 dp[i][j-1]dp[i-1]就是dp[i-1][j]所以对于dp[i]的求解就变为 当 i 0时dp[ j ] dp[j] s1.charAt(i-1)s3.charAt(ij-1)当 j 0时dp[ j ] | dp[ j-1 ] s2.charAt(j-1) s3.charAt(ij-1)
AC代码
class Solution {public static boolean isInterleave(String s1, String s2, String s3) {if (s1.length() s2.length() ! s3.length()) {return false;}if (s1.length() 0 || s2.length() 0) {return s3.equals(s1) || s3.equals(s2);}boolean[]dp new boolean[s2.length() 1];dp[0]true;for (int i 0; i s1.length(); i) {for (int j 0; j s2.length(); j) {if (i 0) {dp[j] dp[j] s1.charAt(i-1) s3.charAt(i j - 1);}if (j 0) {dp[j] | dp[j - 1] s2.charAt(j-1) s3.charAt(i j - 1);}}}return dp[s2.length()];}
}
