课程推荐：PHP开发工程师--学习猿地精品课程

题目描述：
给定三个字符串 s1, s2, s3, 验证 s3 是否是由 s1 和 s2 交错组成的。

测试样例：
输入：

s1 = "accccaabbccabccabbcaabaabccccbbcabcabaccccabcaccbbccaaaccab"

s2 = "cbaccbcaaaaacabbbbaaaccbabbcbcbbbbbbabcbbabaababaa"

s3 = "cbaccbcaaccaaccaabbcacacaabbbbbaccaaacbcbabbbcbccaabbaabbbbcccbbcabbbcbcababbcaabaabcabacaccabcaccbbccaaaccab"

输出：

true

输入: s1 = "aabcc", s2 = "dbbca", s3 = "aadbbbaccc"

输出: false

输入: s1 = "aabcc", s2 = "dbbca", s3 = "aadbbcbcac"

输出: true

方案1：
动态规划问题，构建二维dp，记录状态，dp[0][0]开始，到dp[s1.length][s2.length]结束，dp[i][j] 记录s3的前i+j个元素是否由s1的前i个和s2的前j个元素组成，dp[i][j] 为ture的条件是：

如果等于s1的第i一个元素，即s3[i+j-1] = s1[i-1],当dp[i-1][j]为true时（当s3的前i+j-1个元素是由s1的前i-1个元素和s2的前j各元素组成为真时），dp[i][j] = true,

同理如果等于s2的第j一个元素，即s3[i+j-1] = s2[j-1],当dp[i][j-1]为true时，dp[i][j] = true（dp[i][j]的状态依赖于前面素状态dp[i-1][j] 和dp[i][j-1]，最终起始于dp[0][0],终止于dp[s1.length][s2.length],dp[s1.length][s2.length]的状态就是本题答案）。

初始化dp:

dp[0][0] = true （s3的第0个元素由s1的第0个元素和s2的第0个元素构成，都为空）

递推公式：

dp[i][j] = (dp[i-1][j] == true && (s3[i+j-1] == s1[i-1])) || (dp[i][j-1] == true && (s3[i+j-1] == s2[j-1]))

以 s1 = "aabcc", s2 = "dbbca", s3 = "aadbbbaccc" 为例

初始状态

[ [ true, false, false, false, false, false ],

[ false, false, false, false, false, false ],

[ false, false, false, false, false, false ],

[ false, false, false, false, false, false ],

[ false, false, false, false, false, false ],

[ false, false, false, false, false, false ] ]

遍历后状态

[ [ true, false, false, false, false, false ],

[ true, false, false, false, false, false ],

[ true, true, true, true, true, false ],

[ false, true, true, false, true, false ],

[ false, false, true, true, true, true ],

[ false, false, false, true, false, true ] ]

js代码

var isInterleave1 = function(s1, s2, s3) {
if(s1.length + s2.length != s3.length){
return false;
}
var dp = new Array(s1.length+1).fill([]);
dp = dp.map(function(item){
return Array(s2.length+1).fill(false)
})
dp[0][0] = true;
for(var i=0;i<=s1.length;i++){
for(var j=0;j<=s2.length;j++){
if(i>0 && j>0){
dp[i][j] = (s3[i+j-1] == s1[i-1] && dp[i-1][j] == true) || (s3[i+j-1] == s2[j-1] && dp[i][j-1] == true);
}else if(i==0 && j>0){
dp[i][j] = s3[i+j-1] == s2[j-1] && dp[i][j-1] == true;
}else if(j==0 && i>0){
dp[i][j] = s3[i+j-1] == s1[i-1] && dp[i-1][j] == true;
}

    }
}
return dp[s1.length][s2.length];

}
php代码

function isInterleave($s1,$s2,$s3){
$len1 = strlen($s1);
$len2 = strlen($s2);
$len3 = strlen($s3);
if($len1 + $len2 != $len3){
return false;
}
$dp = array_fill(0,$len1+1,array_fill(0,$len2+1,false));
$dp[0][0] = true;
for($i=0;$i<=$len1;$i++){
for($j=0;$j<=$len2;$j++){
if($i>0 && $j>0){
$dp[$i][$j] = ($s3[$i+$j-1] == $s1[$i-1] && $dp[$i-1][$j] == true) || ($s3[$i+$j-1] == $s2[$j-1] && $dp[$i][$j-1] == true);
}else if($i==0 && $j>0){
$dp[$i][$j] = $s3[$i+$j-1] == $s2[$j-1] && $dp[$i][$j-1] == true;
}else if($i>0 && $j==0){
$dp[$i][$j] = $s3[$i+$j-1] == $s1[$i-1] && $dp[$i-1][$j] == true;
}
}
}
return $dp[$len1][$len2];
}
方案2
递归思路，逐个从s1，s2取出元素组成s3,[0,1)s1以经选取的元素，[0,k2)s2已经选取的元素，[0,k3)s3已经组成元素，从function(k1=0,k2=0,k3=0)开始，如果s1[k1] != s3[k3] && s1[k2] != s3[k3],返回false，(k1,k2)这个组合不成立，返回false，如果s1[k1] = s3[k3]，选取k1作为s3的k3元素,k1+1,k3+1,function(k1+1,k2,k3+1)继续判断状态，同理s2[k2] = s3[k3]，选取k2作为s3的k3元素,k2+1,k3+1,function(k1,k2+1,k3+1)继续判断状态，当s2[k2] = s3[k3]，s2[k1] = s3[k3]，同时成立时，分别function(k1,k2+1,k3+1)，function(k1+1,k2,k3+1)计算

终止条件，当k1>=s1.length && k2>=s2.length 说明s1，s2都遍历到结尾了，s1,s2的所有元素够能归属到s3,可以返回true，如果所有的遍历都没有返回true，总结果返回false

为了规避重复计算，通过一个二维数组记录状态，当k1,k2组合为false时，dp[k1][k2] = fasle,再碰到k1,k2组合时，直接返回false，不在重复计算。

js代码

var isInterleave = function(s1, s2, s3) {
if(s1.length + s2.length != s3.length){
return false;
}

var dp = new Array(s1.length+2).fill([]);
dp = dp.map(function(item){
    return Array(s2.length+2).fill(true)
})
var status = false;
var recursion = function(k1,k2,k3){
    var res = false;
    if(k1>=s1.length && k2>=s2.length){
        status=true;
        return;
    }
    if(status){
        return;
    }
    if(s1[k1] != s3[k3] && s2[k2] != s3[k3]){
        dp[k1][k2] = false;
        return false;
    }
    if(s1[k1] == s3[k3] && k1<s1.length && dp[k1+1][k2] != false){
        res = recursion(k1+1,k2,k3+1);    
    }
    if(s2[k2] == s3[k3] && k2<s2.length && dp[k1][k2+1] != false){
        res = recursion(k1,k2+1,k3+1) || res;    
    }
    dp[k1][k2] = res;
    return res;
}

recursion(0,0,0);
return status;
console.log(status);

}

php代码

function isInterleave($s1, $s2, $s3) {
global $len1,$len2,$len3,$s1,$s2,$s3,$status,$dp;
$len1 = strlen($s1);
$len2 = strlen($s2);
$len3 = strlen($s3);
if($len1 + $len2 != $len3){
return false;
}
$dp = array_fill(0,$len1+2,array_fill(0,$len2+2,true));
//初始化status
$status = false;
function recursion($k1,$k2,$k3){
global $len1,$len2,$len3,$s1,$s2,$s3,$status,$dp;
$res = false;
//满足最终条件，返回true
if($k1>=$len1 && $k2>=$len2){
$status = true;
return true;
}
//status以经为true，停止计算
if($status == true){
return;
}
if($s1[$k1] != $s3[$k3] && $s2[$k2] != $s3[$k3]){
$dp[$k1][$k2] = false;
return false;
}
if($s1[$k1] == $s3[$k3] && $k1<$len1 && $dp[$k1+1][$k2] != false){
$res = recursion($k1+1,$k2,$k3+1);
}
if($s2[$k2] == $s3[$k3] && $k2<$len2 && $dp[$k1][$k2+1] != false){
$res = recursion($k1,$k2+1,$k3+1) || $res;
}
$dp[$k1][$k2] = $res;
return $res;
}

recursion(0,0,0);
return $status;

}

文章来自：https://zhuanlan.zhihu.com/p/44299471