2015年10月2日星期五

Leetcode 97 Interleaving String

Given s1s2s3, 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.
Solution 1: Use DP, dp[i][j] store the result of s1[0...i) s2[0..j) and s3[0...i+j) is interleaving or not. There will be 2 case, s1.charAt(i-1)==s3.charAt(i+j-1) or s2.charAt(j-1)==s3.charAt(i+j-1). Details below:
 public class Solution {  
   public boolean isInterleave(String s1, String s2, String s3) {  
     int m=s1.length();  
     int n=s2.length();  
     if (m+n!=s3.length()) return false;  
     boolean[] dp=new boolean[n+1];  
     for (int i=0; i<=m; i++) {  
       for (int j=0; j<=n; j++) {  
         if (i==0) {  
           if (j==0) dp[j]=true;  
           else dp[j]=s2.charAt(j-1)==s3.charAt(j-1) && dp[j-1];  
         }  
         else if (j==0) dp[j]=s1.charAt(i-1)==s3.charAt(i-1) && dp[j];  
         else dp[j]=(s1.charAt(i-1)==s3.charAt(i+j-1) && dp[j]) || (s2.charAt(j-1)==s3.charAt(i+j-1) && dp[j-1]);  
       }  
     }  
     return dp[n];  
   }  
 }  

没有评论:

发表评论