Saturday, January 10, 2015

Interleaving String (LeetCode String)

Question: 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.

Idea: Dynamic programming. Let dp[i][j] denote whether s3[0...i+j-1] is a interleaving of s1[0...i-1] and s2[0...j-1]. Then we have the following recursion function:
dp[i][j]==true requires either
1) dp[i-1][j]==true && s1[i-1]==s3[j+i-1];
or 2) dp[i][j]==true && s2[i-1]==s3[i+j-1].
For the first row and first column, since the other string is empty, actually we are doing string.equals() one character by one character.

Time: O(n^2) Space: O(n^2)

Code: 
 public class Solution {  
   public boolean isInterleave(String s1, String s2, String s3) {  
     int m=s1.length();  
     int n=s2.length();  
     if(s3.length()!=m+n)  
       return false;  
     boolean[][] dp=new boolean[m+1][n+1];  
     dp[0][0]=true;  
     for(int i=0;i<m;i++)  
     {  
       if(s1.charAt(i)==s3.charAt(i))  
         dp[i+1][0]=true;  
       else  
         break;  
     }  
     for(int j=0;j<n;j++)  
     {  
       if(s2.charAt(j)==s3.charAt(j))  
         dp[0][j+1]=true;  
       else  
         break;  
     }  
     for(int i=1;i<=m;i++)  
     {  
       for(int j=1;j<=n;j++)  
       {  
         dp[i][j]=(dp[i-1][j]&&s1.charAt(i-1)==s3.charAt(j+i-1))  
         ||(dp[i][j-1]&&s2.charAt(j-1)==s3.charAt(i+j-1));  
       }  
     }  
     return dp[m][n];  
   }  
 }  

No comments:

Post a Comment