leetcode97 交错字符串

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

示例 1:

输入: s1 = "aabcc", s2 = "dbbca", s3 = "aadbbcbcac"
输出: true
示例 2:

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

思路：之前做过，比较简单，dp[i][j]代表s1的i个和s2的j个能不能组成。

对于s3的i+j如何组成，只能：

1）i+j-1已经被i和j-1组成，s2[j]==s3[i+j]

比如：

s1:123 s2 456 s3:12453  6

2）i+j-1已经被i-1和j组成，s1[i]==s3[i+j]

比如：s1:126 s2 453 s3:12453  6

压缩空间后的表现还是不理想，搞不懂为什么。

  

   

    

     

    
    

     

      public class Solution {
     
    
   

    

     

    
    

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

    

     

    
    

     
 int len1=s1.length();
     
    
   

    

     

    
    

     
 int len2=s2.length();
     
    
   

    

     

    
    

     
 int len3=s3.length();
     
    
   

    

     

    
    

     
 if (len3 != len1 + len2) {
     
    
   

    

     

    
    

     
 return false;
     
    
   

    

     

    
    

     

       }
     
    
   

    

     

    
    

     
 boolean dp[] = new boolean[s2.length() + 1];
     
    
   

    

     

    
    

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

    

     

    
    

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

    

     

    
    

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

    

     

    
    

     

       dp[j] = true;
     
    
   

    

     

    
    

     

       } else if (i == 0) {
     
    
   

    

     

    
    

     

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

    

     

    
    

     

       } else if (j == 0) {
     
    
   

    

     

    
    

     

       dp[j] = dp[j] && s1.charAt(i - 1) == s3.charAt(i + j - 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[s2.length()];
     
    
   

    

     

    
    

     

         }
     
    
   

    

     

    
    

     

      }
     
    
  
 

文章来源: fantianzuo.blog.csdn.net，作者：兔老大RabbitMQ，版权归原作者所有，如需转载，请联系作者。

原文链接：fantianzuo.blog.csdn.net/article/details/103257370