Leetcode Interleaving String

Interleaving String

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.

这种题目应该立即反应需要动态规划法，会填表，然后翻译为程序。可以用递归法求解，但是会超时，而且好像都不容易写。

不过这里是三个字符串，应该如何设计这个表是个大问题。

这里用s1和s2作为二维表的两个维的下标，然后徐两个下标相加得到s3的一维下标，进行比较字符。这是本题关键，也是这个表这么难设计，所以本题的难度还是很高的。对没接触过这类题目的人来说，应该是五星级难度的题目了。

	bool isInterleave(string s1, string s2, string s3) 
	{
		int n1 = s1.length(), n2 = s2.length(), n3 = s3.length();
		if (n1+n2 != n3) return false;

		vector<vector<bool> > ta(n1+1, vector<bool>(n2+1));
		ta[0][0] = true;
		for (int i = 1; i <= n2; i++)
		{
			if (ta[0][i-1] && s2[i-1] == s3[i-1]) ta[0][i] = true;
			else break;
		}
		for (int i = 1; i <= n1; i++)
		{
			if (ta[i-1][0] && s1[i-1]==s3[i-1]) ta[i][0] = true;
			for (int j = 1; j <= n2; j++)
			{
				if (ta[i][j-1] && s2[j-1] == s3[i+j-1]) ta[i][j] = true;
				else if (ta[i-1][j] && s1[i-1] == s3[i+j-1]) ta[i][j] = true;
			}
		}
		return ta[n1][n2];
	}

直接研究如何设计表， 如何填写表，最后写程序。

会设计3个字符串的表的思路。

//2014-2-15 update
	bool isInterleave(string s1, string s2, string s3) 
	{
		if (s1.length() + s2.length() != s3.length()) return false;
		bool *A[2];
		A[0] = new bool[s1.length()+1];
		A[1] = new bool[s1.length()+1];
		A[0][0] = true;
		for (int i = 0; i < s1.length(); i++)
		{
			if (A[0][i] && s1[i] == s3[i]) A[0][i+1] = true;
			else A[0][i+1] = false;
		}
		bool idx = false;
		for (int i = 0; i < s2.length(); i++)
		{
			idx = !idx;
			if (s2[i] == s3[i] && A[!idx][0]) A[idx][0] = true;
			else A[idx][0] = false;

			for (int j = 0; j < s1.length(); j++)
			{
				if (s2[i] == s3[i+j+1] && A[!idx][j+1]) A[idx][j+1] = true;
				else if (s1[j] == s3[i+j+1] && A[idx][j]) A[idx][j+1] = true;
				else A[idx][j+1] = false;
			}
		}
		return A[idx][s1.length()];
	}