97。InterleavingStringss3，验证s3是否由s1和s2交错组成。示例1：输入：s1="aabcc",s2="dbbca",s3="aadbbcbcac"输出：true示例2：输入：s1="aabcc",s2="dbbca",s3="aadbbbaccc"输出：false解题思路：动态规划这里我们用不同路径的思想来解题，向右下移，找出是否存在这样一条路径。那么这个问题就可以转化为一个验证，s3是否可以从下面选择s1，从右边选择s2，这种形式，求是否有s3的路径。状态定义设置dp[i][j]表示s1的前i个字符和s2的前j个字符可以拼接成s3(i+j)个字符，即当前路径存在。状态转移方程如果s1的第i个元素等于s3的第i+j个元素，那么dp[i][j]是否为真取决于dp[i-1][j]是否为真，也就是说，这里需要看s1的前i-1个元素和s2的前j个元素是否可以拼接成s3的前i+j-1个元素。同理，如果s2的第j个元素等于s3的第i+j个元素，此时dp[i][j]是否为真，需要看dp[i][j-1]是否为真，也就是你需要看s2的前i个元素和s2的前j-1个元素是否可以拼接成s3的前i+j-1个元素。那么最终的状态转移方程为：dp[i][j]=(dp[i-1][j]ands3[i+j-1]=s1[i-1])or(dp[i][j-1]ands3[i+j-1]=s2[j-1])状态初始化dp0=True如果j=0，dpi是否成立取决于dpi-1和s1的第i个字符是否等于s3如果i=0，dp0是否成立取决于dp0和s3的第i个字符是否等于s2的第i个字符。具体实现代码如下。代码实现类Solution:defisInterleave(self,s1:str,s2:str,s3:str)->bool:#先处理特殊情况，如果s1和s2的长度之和不等于s3的长度,返回假。因为不能交错如果len(s1)+len(s2)!=len(s3):returnFalsem=len(s1)n=len(s2)#statedefinitiondp=[[False]*(n+1)for_inrange(m+1)]#初始化dp[0][0]=Trueforiinrange(1,m+1):dp[i][0]=dp[i-1][0]ands3[i-1]==s1[i-1]forjinrange(1,n+1):dp[0][j]=dp[0][j-1]ands3[j-1]==s2[j-1]foriinrange(1,m+1):forjinrange(1,n+1):dp[i][j]=(dp[i-1][j]ands3[i+j-1]==s1[i-1])或者(dp[i][j-1]ands3[i+j-1]==s2[j-1])返回dp[-1][-1]欢迎大家关注结果公众号【图书收藏】
