LeetCode 97 交错字符串 Interleaving String

    技术2022-07-11  100

    LeetCode 97 交错字符串 Interleaving String

    题目描述

    Given s1, s2, s3, find whether s3 is formed by the interleaving of s1 and s2. 本题给定3个字符串,求第三个能否由前两个交错的组成。示例如下:

    Example 1:

    Input: s1 = “aabcc”, s2 = “dbbca”, s3 = “aadbbcbcac” Output: true

    Example 2:

    Input: s1 = “aabcc”, s2 = “dbbca”, s3 = “aadbbbaccc” Output: false

    对于例1,s3首先从s1获取“aa”,从s2获取“dbbc“,再从s1获取”bc“,从s2获取”a“,从s1获取”c“。s3能够交错的从s1和s2按顺序取元素组成。

    因此,s3能否由s1和s2交错组成,可以看做是两个指针分别从s1和s2起始位置开始,如果其中一个与s3对应元素相同,就将指针前移,继续判断剩下的部分。这实际上是一种递归搜索的策略,那么对应的,通过记忆化的方法,能够找到更快的动态规划解法。

    对于这类有两个字符串、数组之类相互折腾的的问题,很多大佬都提出了类似的看法,二维动规可解! 不妨假设 d p [ i ] [ j ] dp[i][j] dp[i][j]表示s1从头到 i − 1 i-1 i1和s2从头到 j − 1 j-1 j1能否交错表示s3从头到 i + j − 1 i+j-1 i+j1,这里之所以有-1是因为要考虑空串的情况。 那么 d p [ i ] [ j ] dp[i][j] dp[i][j]怎么求呢?显然计算这里时我们已经知道了 d p [ i − 1 ] [ j ] dp[i-1][j] dp[i1][j] d p [ i ] [ j − 1 ] dp[i][j-1] dp[i][j1]的结果,那么如果 d p [ i − 1 ] [ j ] dp[i-1][j] dp[i1][j]为true,也就是可以交错表示,此时如果 s 1 [ i − 1 ] = = s 3 [ i + j − 1 ] s1[i-1]==s3[i+j-1] s1[i1]==s3[i+j1]表明在 d p [ i − 1 ] [ j ] dp[i-1][j] dp[i1][j]基础上可以从s1再取一个元素且与s3对应位置是相等的,那说明 d p [ i ] [ j ] dp[i][j] dp[i][j]也能够组成,为true,同理在 d p [ i ] [ j − 1 ] dp[i][j-1] dp[i][j1]为true时 s 2 [ j − 1 ] = = s 3 [ i + j − 1 ] s2[j-1]==s3[i+j-1] s2[j1]==s3[i+j1]则是从s2取一个元素,同样可行,二者是或的关系,满足一个即可,均不满足那就说明 d p [ i ] [ j ] dp[i][j] dp[i][j]是false。最后只需要查看 d p [ s 1. s i z e ( ) ] [ j = s 2. s i z e ( ) ] dp[s1.size()][j=s2.size()] dp[s1.size()][j=s2.size()]即可。

    当然对于本题,首先可以判断三个字符串的长度关系,如果 s 1. s i z e ( ) + s 2. s i z e ( ) ≠ s 3. s i z e ( ) s1.size()+s2.size()\ne s3.size() s1.size()+s2.size()=s3.size()那显然是不可能实现的。 接下来考虑边界情况,首先 d p [ 0 ] [ 0 ] dp[0][0] dp[0][0]表示两个空串个能否组成一个空串,显然可以,为true; 对于s1为空的情况: d p [ 0 ] [ j ] = d p [ 0 ] [ j − 1 ] & & ( s 2 [ j − 1 ] = = s 3 [ j − 1 ] ) dp[0][j] = dp[0][j - 1] \& \& (s2[j - 1] == s3[j - 1]) dp[0][j]=dp[0][j1]&&(s2[j1]==s3[j1]) 同理s2为空: d p [ i ] [ 0 ] = d p [ i − 1 ] [ 0 ] & & ( s 1 [ i − 1 ] = = s 3 [ i − 1 ] ) dp[i][0] = dp[i - 1][0] \&\& (s1[i - 1] == s3[i - 1]) dp[i][0]=dp[i1][0]&&(s1[i1]==s3[i1]) 其他情况按照上述的转移方程遍历即可。C++代码如下:

    bool isInterleave(string s1, string s2, string s3) { int l1 = s1.size(), l2 = s2.size(), l3 = s3.size(); if ((l1 + l2) != l3) return false; vector<vector<bool>>dp(l1 + 1, vector<bool>(l2)); //dp[i][j] means if s3(0 - i+j-1) is formed by the interleaving of s1(0,i-1) and s2(0,j-1) dp[0][0] = true; for (int i = 1; i <= l1; ++i) dp[i][0] = dp[i - 1][0] && (s1[i - 1] == s3[i - 1]); for (int j = 1; j <= l2; ++j) dp[0][j] = dp[0][j - 1] && (s2[j - 1] == s3[j - 1]); for (int i = 1; i <= l1; ++i) { for (int j = 1; j <= l2; ++j) { dp[i][j] = (dp[i - 1][j] && (s1[i - 1] == s3[i - 1 + j])) || (dp[i][j - 1] && (s2[j - 1] == s3[j - 1 + i])); } } return dp[l1][l2]; }
    Processed: 0.017, SQL: 9