Leetcode-Complete-Guide/code/97.txt at master · JunBinLiang/Leetcode-Complete-Guide · GitHub

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
26
27
28
29
30
31
class Solution {
    public boolean isInterleave(String s1, String s2, String s3) {
        if(s1.length()+s2.length()!=s3.length())return false;

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

        dp[0][0]=true;

        for(int i=1;i<dp.length;i++){
            if(s1.charAt(i-1)==s3.charAt(i-1)&&dp[i-1][0])dp[i][0]=true;
        }

        for(int i=1;i<dp[0].length;i++){
            if(s2.charAt(i-1)==s3.charAt(i-1)&&dp[0][i-1])dp[0][i]=true;
        }

        for(int i=1;i<dp.length;i++){
            char c1=s1.charAt(i-1);
            for(int j=1;j<dp[0].length;j++){
                char c2=s2.charAt(j-1);
                char c3=s3.charAt(i+j-1);

                if(c1==c3&&dp[i-1][j])dp[i][j]=true;
                if(c2==c3&&dp[i][j-1])dp[i][j]=true;
            }
        }


        return dp[s1.length()][s2.length()];
    }
}