97. Interleaving String

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.

思路：If we can find a way that all of the chars of s3 comes from s1 or s2, then we can form s3 by interleaving s1 and s2, and thus return true; otherwise we return false. For example, if s1 = abc, s2 = bcd, s3 = abbccd, then s3 can be formed by "001011" or "010101". (0 represents char comes from s1, and 1 represents char comes from s2).

首先看个会超时的解熟悉熟悉思路

public class Solution {
    public boolean isInterleave(String s1, String s2, String s3) {
        if (s1==null||s1.length()==0){
            return s2.equals(s3);
        }
        if (s2==null||s2.length()==0){
            return s1.equals(s3);
        }

        if (s3.charAt(0)==s1.charAt(0) && s3.charAt(0)==s2.charAt(0)){
            return isInterleave(s1.substring(1),s2,s3.substring(1)) || isInterleave(s1,s2.substring(1),s3.substring(1));
        }else if (s3.charAt(0)==s1.charAt(0)){
            return isInterleave(s1.substring(1),s2,s3.substring(1));
        }else if (s3.charAt(0)==s2.charAt(0)){
            return isInterleave(s1,s2.substring(1),s3.substring(1));
        }
        return false;
    }
}

这个解不超时，引入hashset避免重复

public class Solution {
      private static Set<Integer> visited; // The combination of i1, i2 has been visited and return false
    public static boolean isInterleave(String s1, String s2, String s3) {
        if(s3.length() != s1.length() + s2.length())
            return false;
        visited = new HashSet<Integer>();
        return isInterleave(s1, 0, s2, 0, s3, 0);
    }

    private static boolean isInterleave(String s1, int i1, String s2, int i2, String s3, int i3)
    {    
        int hash = i1 * s3.length() + i2;
        if(visited.contains(hash))
            return false;

        if(i1 == s1.length())
            return s2.substring(i2).equals(s3.substring(i3));
        if(i2 == s2.length())
            return s1.substring(i1).equals(s3.substring(i3));

        if(s3.charAt(i3) == s1.charAt(i1) && isInterleave(s1, i1+1, s2, i2, s3, i3+1) ||
           s3.charAt(i3) == s2.charAt(i2) && isInterleave(s1, i1, s2, i2+1, s3, i3+1))
            return true;

        visited.add(hash);
        return false;
    }
}