字符串交错

 

题目：对于三个字符串A，B，C。我们称C由A和B交错组成当且仅当C包含且仅包含A，B中所有字符，且对应的顺序不改变。请编写一个高效算法，判断C串是否由A和B交错组成   "ABC",3,"12C",3,"A12BCC",6   返回：true

思路：维护两个指针即可，但是while循环的跳出条件和结束循环返回的条件有点不好想，要多模拟下。。。

 　　　　在leetcode上看到这道题了，按照我的思路用两个指针的话，解决不了例如"aa","ab"和"aaba"这种情况，所以要用dp。。。。

　　dp[i][j]代表s1在i处时s2在j处是否与s3在i+j处一样,第0个意味着空字符

public boolean isInterleave(String s1, String s2, String s3) {
        int n=s1.length(),m=s2.length(),k=s3.length();
        if(n+m!=k) return false;
        boolean[][] dp=new boolean[n+1][m+1];
        dp[0][0]=true;
        for(int i=1;i<=n;i++){
           dp[i][0]=dp[i-1][0]&&(s1.charAt(i-1)==s3.charAt(i-1));
        }
        for(int i=1;i<=m;i++){
            dp[0][i]=dp[0][i-1]&&(s2.charAt(i-1)==s3.charAt(i-1));
        }
        for(int i=1;i<=n;i++){
            for(int j=1;j<=m;j++){
                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[n][m];
    }