Givens1,s2,s3, find whethers3is formed by the interleaving ofs1ands2.

For example,
Given:
s1="aabcc",
s2="dbbca",

Whens3="aadbbcbcac", return true.
Whens3="aadbbbaccc", return false.

tag: BFS, DFS, DP

class Solution {
    public boolean isInterleave(String s1, String s2, String s3) {
        if (s1.length() + s2.length() != s3.length()) return false;
        Set<Integer> hash = new HashSet<>();
        return dfs(s1, s2, s3, 0, 0, hash);
    }

    private boolean dfs(String s1, String s2, String s3, int index1, int index2, Set<Integer> hash){
        if (index1 + index2 == s3.length()){
            return true;
        }
        if (hash.contains(index1 * s3.length() + index2)){
            return false;
        }

        hash.add(index1 * s3.length() + index2);
        boolean match1 = index1 < s1.length() && s1.charAt(index1) == s3.charAt(index1 + index2);
        boolean match2 = index2 < s2.length() && s2.charAt(index2) == s3.charAt(index1 + index2);

        if (match1 && match2){
            return dfs(s1, s2, s3, index1 + 1, index2, hash) || dfs(s1, s2, s3, index1, index2 + 1, hash);
        }
        else if (match1){
            return dfs(s1, s2, s3, index1 + 1, index2, hash);
        }
        else if (match2){
            return dfs(s1, s2, s3, index1, index2 + 1, hash);
        }
        else{
            return false;
        }
    }
}

要特别注意： hash.add(index1 * s3.length() + index2);

是index1 * s3,length() + index2 而不是 index1 * s2.length() + index2

是因为 s1 = aa, s2 = ab, s3 = aaba, index1 = 0, index2 = 2 和 index1 = 1, index2 = 0