[leetcode]97

#include <iostream>
#include <vector>
#include <set>
using namespace  std;

//dp解法

int find(int i, int j, int k, vector<vector<int> >& dp, string& s1, string& s2, string& s3) {
    if (k == 0)
        return true;
    if (dp[i][j] != -1)
        return dp[i][j];

    dp[i][j] = 0;

    if (i != 0 && s1[i - 1] == s3[k - 1])
        dp[i][j] = dp[i][j] || find(i - 1, j, k - 1, dp, s1, s2, s3);

    if (j != 0 && s2[j - 1] == s3[k - 1])
        dp[i][j] = dp[i][j] || find(i, j - 1, k - 1, dp, s1, s2, s3);

    return dp[i][j];
}

//给定三个字符串,s1 and s2 是不是交叉存在于s3中
bool isInterleave(string s1, string s2, string s3) {
    if (s1.length() + s2.length() != s3.length())
        return false;
    vector<vector<int> >dp(s1.size() + 1, vector<int>(s3.size() + 1, -1));
    return find(s1.size(), s2.size(), s3.size(), dp, s1, s2, s3) == 0 ? false : true;
}

int main()
{
    string s1 = "aabcc";
    string s2 = "dbbca";
    string s3 = "aadbbcbcac";

    bool re = isInterleave(s1, s2, s3);
    cout << boolalpha<<re;
    return 0;
}

Runtime: 4 ms, faster than 78.39% of C++ online submissions for Interleaving String.
Memory Usage: 9.6 MB, less than 7.14% of C++ online submissions for Interleaving String.