97. Interleaving String

Posted on | Edited on | Views:

LeetCode

Approach 1: Brute Force

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
class Solution {
    private boolean util(String s1, int i, String s2, int j, String s3, String res) {
        if (res.equals(s3) && i == s1.length() && j == s2.length()) {
            return true;
        }
        boolean ans = false;
        if (i < s1.length()) {
            ans |= util(s1, i + 1, s2, j, s3, res + s1.charAt(i));
        }
        if (j < s2.length()) {
            ans |= util(s1, i, s2, j + 1, s3, res + s2.charAt(j));
        }
        return ans;
    }

    public boolean isInterleave(String s1, String s2, String s3) {
        return util(s1, 0, s2, 0, s3, "");
    }
}

Approach 2: Recursion with memoization

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
class Solution {
    private boolean isInterleaveUtil(String s1,int i,String s2,int j,String s3,int k,int[][] memo){
        if(i==s1.length()) return s2.substring(j).equals(s3.substring(k));
        if(j==s2.length()) return s1.substring(i).equals(s3.substring(k));
        if(memo[i][j]!=-1) return memo[i][j]==0?false:true;
        boolean ans = false;
        if (s3.charAt(k) == s1.charAt(i) && isInterleaveUtil(s1, i + 1, s2, j, s3, k + 1, memo)
            || s3.charAt(k) == s2.charAt(j) && isInterleaveUtil(s1, i, s2, j + 1, s3, k + 1, memo)) {
            ans = true;
        }
        //store the value returned by the recursive functions in the memoization array memo appropriatelys so 
        //that when it is encountered the next time, the recursive function won't be called
        memo[i][j] = ans ? 1 : 0;
        return ans;
    }
    public boolean isInterleave(String s1, String s2, String s3) {
        int[][] memo=new int[s1.length()][s2.length()];
        for(int i=0;i<s1.length();i++){
            for(int j=0;j<s2.length();j++){
                memo[i][j]=-1;
            }
        }
        return isInterleaveUtil(s1,0,s2,0,s3,0,memo);
    }
}

Approach 3: Using 2D Dynamic Programming

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
class Solution {
    public boolean isInterleave(String s1, String s2, String s3) {
        int lens1=s1.length(),lens2=s2.length(),lens3=s3.length();
        if(lens1+lens2!=lens3) return false;
        boolean[][] dp=new boolean[lens1+1][lens2+1];
        for(int i=0;i<=lens1;i++){
            for(int j=0;j<=lens2;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-1][j]&&s1.charAt(i-1)==s3.charAt(i+j-1)||
                             dp[i][j-1]&&s2.charAt(j-1)==s3.charAt(i+j-1);
                }
            }
        }
        return dp[lens1][lens2];
    }
}

0%