Given s1, s2, s3, find whether s3 is formed by the interleaving of s1 and s2.

Example 1:

Input: s1 = “aabcc”, s2 = “dbbca”, s3 = “aadbbcbcac”
Output: true
Example 2:

Input: s1 = “aabcc”, s2 = “dbbca”, s3 = “aadbbbaccc”
Output: false

字符串和匹配结合的题目一般都是DP思路，如果使用回溯暴力搜索必然是超时。
但是这道题不是典型的DP思路，很难直接构造出DP的状态转移方程，对于我来说一时半会是无法想清楚子问题到底是什么。所以先来说说能够想清楚的思路。

这道题目虽然看起来回溯搜索的时间复杂度是指数阶，但是使用cache剪枝之后的复杂度大大降低。首先是带cache的DFS，这个思路很清晰就是按照先看s1能不能匹配上当前的位置，如果能则递归下一个位置，如果不能则看s2能不能匹配当前位置如果能则递归下去。递归向下搜索，回溯向上返回，每走到一个可行位置都是我们需要向下搜索的位置，但是一旦一个位置我们已经确定不可能成功了还需要再往下走么？当然不能往下再走了，因为这将是重复路线，所以所有递归返回是false的路线需要将其记录到cache当中，同时每次递归的开始需要判断当前位置是不是在cache当中如果在直接返回false。至于怎么存储路线，其实也不需要真的存储路线，只需要存储当前匹配的i,j位置，然而set我们只希望存一个值，所以存下i*N+j，这样可以避免可能的不同位置映射的冲突。

带cache的DFS

class Solution {
public:
    /* 判断s3是否可以由s1和s2插入组成，s1,s2后续的顺序和原始顺序一致 */
    
    bool dfs(string& s1,string& s2,string& s3,int i,int j,int k,unordered_set<int>& s) {
        int key = i*s3.size() + j;
        if(s.count(key)) return false;
        if(i==s1.size()) return s2.substr(j) == s3.substr(k);
        else if(j==s2.size()) return s1.substr(i) == s3.substr(k);
        else {
            if(s1[i]==s3[k]&&dfs(s1,s2,s3,i+1,j,k+1,s)||s2[j]==s3[k]&&dfs(s1,s2,s3,i,j+1,k+1,s))
                return true;
        }
        s.insert(key);
        return false;
    }
    
    bool isInterleave(string s1, string s2, string s3) {
        int N = s3.size();
        int n = s1.size(),m = s2.size();
        if(n+m!=N) return false;
        unordered_set<int> s;
        bool res = dfs(s1,s2,s3,0,0,0,s);
        return res;
    }
};

BFS的话就是使用一个queue和cache，queue进行每一层节点的入队，cache进行存储每一层我们到达的可行节点位置，因为我们只希望每一个可能成为下一个位置的节点只入队一次，所以需要不希望一个位置进队列多次，所以每一个位置节点入队之后就将其位置存入cache当中，在每次放入队列之前判断这个位置是不是已经在cache当中也就是处理过了，如果没有处理过就放入队列等待遍历到下一层的时候处理，BFS的时间复杂度在整体上是和DFS一样的，每一个位置处理一次，但是DFS当处理到一个可行方案的时候就直接递归返回了，在处理这个是不是，能不能，有没有可行解的方案的题目当中是有先天的优势的，而BFS是需要遍历到最后一层的时候遇到可行解才真正的返回。

带cache的BFS

class Solution {
public:
    /* 判断s3是否可以由s1和s2插入组成，s1,s2后续的顺序和原始顺序一致 */
    
    bool isInterleave(string s1, string s2, string s3) {
        int N = s3.size();
        int n = s1.size(),m = s2.size();
        if(n+m!=N) return false;
        if(N==0&&n+m==N) return true;
        
        unordered_set<int> cache;
        queue<int> q;
        q.push(0);
        int k = 0;
        
        while(!q.empty()) {
            int i = q.front()/N;
            int j = q.front()%N;
            q.pop();
            k = i+j;
            
            if(i<n&&s1[i]==s3[k]&&!cache.count((i+1)*N+j)) {
                cache.insert((i+1)*N+j);
                q.push((i+1)*N+j);
                if(k==N-1)
                    return true;
            }
            if(j<m&&s2[j]==s3[k]&&!cache.count(i*N+j+1)) {
                cache.insert(i*N+j+1);
                q.push(i*N+j+1);
                if(k==N-1)
                    return true;
            }
        }
        
        return false;;
    }
};

最后来说说这道题目的DP做法，这道题目的DP思路我是一开始绞尽脑汁没想出来，当完成DFS，BFS解法之后才真正对这道题目的子问题有一个认识。因为交错字符串有一个限制条件就是s1,s2串如果能够组成s3，其在s3当中字符的相对位置和在原串当中的相对位置必须是一致的不能改变，那么对于s3[k]到底使用哪个串的相应字符进行匹配就有很多种思路，一个是s3[k]可以使用s2还是s3当中的字符进行子问题考虑，但是这样一想，s3[k+1]应该拿谁来匹配还是不知道，因为我不晓得s3[i]是用的哪一个串的哪一个位置啊。进一步想如果我们假设已经知道s3[k]用的s2[i]匹配上，那么f[k+1] = s3[k+1]==s1[i+1] if(f[k]==true), 既然能够这么想那么s3[k]也可是是s2[j]匹配上的，那么 f[k+1] = s3[k+1]==s2[j+1] if(f[k]==true) ,显然这样的1维状态方程是描述不清楚这个问题的，那么应该加到2维来描述s3[k]由s1[i],s2[j]匹配的状况，由于动规的最优子结构的特点我们无需知道s3[k]到底是由s1,s2的那个位置能够匹配上，只要知道如果匹配上了对于s1就是i位置对于s2就是j位置，我们不去向子问题的解是怎么得到的。
这样的话采用f(i,j,k)的递归方式进行描述：
f(i,j,k) 表示s3前k个元素组成的子串目前是否能够被s1,s2组成

f(i,j,k) = (s3[k] == s1[i] && f(i-1,j,k-1)==true)||(s3[k]==s2[j]&&f(i,j-1,k-1)==true)
如果按照上面的状态转移方程进行下去将是3维的DP，我们发现i+j必然是等于k的，因为s1的前i个s2的前j个如果能够和s3的前k个匹配，必然i+j=m。所以3维DP就能够降到2维DP，k用i和j当前的值算出来就可以了。
f(i,j) = (s3[i+j] ==s1[i] && f(i-1,j)==true)| | (s3[i+j]==s2[j]&&f(i,j-1)==true)
自底向上我们就从dp[0][0]开始求出dp[n-1][m-1]即可。每一个位置只和其左边和上面的位置的值有关所以先处理好边界之后一步一步从左往右从上往下的求解就行了。

class Solution {
public:
    bool isInterleave(string s1, string s2, string s3) {
        if (s1.size() + s2.size() != s3.size()) return false;
        int n1 = s1.size();
        int n2 = s2.size();
        vector<vector<bool> > dp(n1 + 1, vector<bool> (n2 + 1, false)); 
        dp[0][0] = true;
        for (int i = 1; i <= n1; ++i) {
            dp[i][0] = dp[i - 1][0] && (s1[i - 1] == s3[i - 1]);
        }
        for (int i = 1; i <= n2; ++i) {
            dp[0][i] = dp[0][i - 1] && (s2[i - 1] == s3[i - 1]);
        }
        for (int i = 1; i <= n1; ++i) {
            for (int j = 1; j <= n2; ++j) {
                dp[i][j] = (dp[i - 1][j] && s1[i - 1] == s3[i - 1 + j]) || (dp[i][j - 1] && s2[j - 1] == s3[j - 1 + i]);
            }
        }
        return dp[n1][n2];
    }
};