LeetCode 97. 交错字符串问题给定三个字符串s1、s2、s3判断s3是否由s1和s2交错interleaving而成——即s3中的字符保持各自在s1、s2中的相对顺序。思路二维 DP设dp[i][j]表示s1的前i个字符和s2的前j个字符能否交错组成s3的前ij个字符。转移s3第ij-1个字符要么来自s1的第i-1个要么来自s2的第j-1个dp[i][j] (dp[i-1][j] s1[i-1]s3[ij-1]) || (dp[i][j-1] s2[j-1]s3[ij-1])边界dp[0][0] true第一行第一列可单独推出。classSolution{publicbooleanisInterleave(Strings1,Strings2,Strings3){intms1.length(),ns2.length();if(mn!s3.length())returnfalse;boolean[][]dpnewboolean[m1][n1];dp[0][0]true;for(inti0;im;i){dp[i1][0]dp[i][0]s1.charAt(i)s3.charAt(i);}for(intj0;jn;j){dp[0][j1]dp[0][j]s2.charAt(j)s3.charAt(j);}for(inti1;im;i){for(intj1;jn;j){dp[i][j](dp[i-1][j]s1.charAt(i-1)s3.charAt(ij-1))||(dp[i][j-1]s2.charAt(j-1)s3.charAt(ij-1));}}returndp[m][n];}}空间优化滚动数组每行只依赖上一行和当前行可将空间降到O(n)classSolution{publicbooleanisInterleave(Strings1,Strings2,Strings3){intms1.length(),ns2.length();if(mn!s3.length())returnfalse;boolean[]dpnewboolean[n1];dp[0]true;for(intj1;jn;j){dp[j]dp[j-1]s2.charAt(j-1)s3.charAt(j-1);}for(inti1;im;i){dp[0]dp[0]s1.charAt(i-1)s3.charAt(i-1);for(intj1;jn;j){dp[j](dp[j]s1.charAt(i-1)s3.charAt(ij-1))||(dp[j-1]s2.charAt(j-1)s3.charAt(ij-1));}}returndp[n];}}复杂度二维版本时间O(m·n)空间O(m·n)滚动数组版时间O(m·n)空间O(n)验证s1 aabcc,s2 dbbca,s3 aadbbcbcac→trues3 aadbbbaccc→false。注意先剪枝m n ! s3.length()否则二维数组可能越界。