[Leetcode][JAVA] Interleaving String

Given s1, s2, s3, find whether s3 is formed by the interleaving of s1 and s2.

For example,
Given:
s1 = "aabcc",
s2 = "dbbca",

When s3 = "aadbbcbcac", return true.
When s3 = "aadbbbaccc", return false.

使用DP, 过程如下图所示：

S2
S1	aadbbcbcac	0 “”	1 d	2 db	3 dbb	4 dbbc	5 dbbca
	0 “”	T	F(d!=a)	F	F	F	F
	1 a	T(a==a)	F(aa)	F	F	F	F
	2 aa	T	T(aad)	T(aadb)
	3 aab	F(aab!=aad)	T(aadb)	T(aadbb)
	4 aabc	F	F(aadbb)	T(aadbbc)
	5 aabcc	F	F(aadbbc)

发现某一格dp[i][j]为true只有当其上面或左边为true才行。且需要新加入的字母与s3新添加的字母一致，True状态才能延续。

代码：

     public boolean isInterleave(String s1, String s2, String s3) {

         int l1=s1.length();

         int l2=s2.length();

         int l3=s3.length();

         if(l1+l2!=l3)

             return false;

         boolean[][] dp = new boolean[l1+1][l2+1];

         for(int i=0;i<=l1;i++) {

             for(int j=0;j<=l2;j++) {

                 if(i==0 && j==0)

                     dp[i][j]=true;

                 else if(i==0)

                     dp[i][j] = dp[i][j-1] && (s2.charAt(j-1)==s3.charAt(i+j-1));

                 else if(j==0)

                     dp[i][j] = dp[i-1][j] && (s1.charAt(i-1)==s3.charAt(i+j-1));

                 else

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

             }

         }

         return dp[l1][l2];

     }

简化为一维数组：

     public boolean isInterleave(String s1, String s2, String s3) {

         int l1 = s1.length();

         int l2 = s2.length();

         int l3 = s3.length();

         if(l3!=(l1+l2))

             return false;

         boolean[] dp = new boolean[l2+1];

         dp[0] = true;

         for(int i=1;i<dp.length;i++)

         {

             dp[i] = dp[i-1] && (s2.charAt(i-1)==s3.charAt(i-1));

         }

         for(int i=1;i<=l1;i++)

         {

             for(int j=0;j<dp.length;j++)

             {

                 if(j==0)

                     dp[j] = dp[j] && (s1.charAt(i-1)==s3.charAt(i-1));

                 else

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

             }

         }

         return dp[l2];

     }

巴特西

[Leetcode][JAVA] Interleaving String

最新文章

热门文章