Interleaving String解题报告

递归解法，需要注意两点：

1、当前要比较的两个元素相等时，需要遍历两条路径，即以(i1 + 1, i2) 和 (i1, i2 + 1)为结点；

2、超时处理机制，设置一个二维数组，记录已经处理过的节点的状态，有三个状态（-1， 0， 1）

1）path[i1][i2] == -1 表示当前节点还未被遍历

2）path[i1][i2] == 0 表示当前节点已遍历并且s3不可能由这条路径组成

3）path[i1][i2] == 1 表示当前节点已遍历且当前节点是可能的路径候选

int isInterleave_(string s1, int i1, string s2, int i2, string s3,
		vector<vector<int>> &path){
		if (path[i1][i2] != -1)	return path[i1][i2];
		if (i1 == s1.length()){
			for (int i = i1 + i2; i < s3.length(); ++i){
				if (s2[i - i1] != s3[i])	{
					path[i1][i2] = 0;
					return 0;
				}
			}
			path[i1][i2] = 1;
			return 1;
		}
		if (i2 == s2.length()){
			for (int i = i1 + i2; i < s3.length(); ++i){
				if (s1[i - i2] != s3[i])	{
					path[i1][i2] = 0;
					return 0;
				}
			}
			path[i1][i2] = 1;
			return 1;
		}
		if (s1[i1] != s2[i2]){
			if (s1[i1] == s3[i1 + i2]){
				path[i1 + 1][i2] = isInterleave_(s1, i1 + 1, s2, i2, s3, path);
				return path[i1 + 1][i2];
			}
			else if (s2[i2] == s3[i1 + i2]){
				path[i1][i2 + 1] = isInterleave_(s1, i1, s2, i2 + 1, s3, path);
				return path[i1][i2 + 1];
			}
			else { path[i1][i2] = 0; return 0; }
		}
		else{
			if (s1[i1] == s3[i1 + i2]){
				path[i1 + 1][i2] = isInterleave_(s1, i1 + 1, s2, i2, s3, path);
				path[i1][i2 + 1] = isInterleave_(s1, i1, s2, i2 + 1, s3, path);
				return path[i1 + 1][i2] || path[i1][i2 + 1];
			}
			else { path[i1][i2] = 0; return 0; }
		}
	}
	bool isInterleave(string s1, string s2, string s3) {
		if (s1.length() + s2.length() != s3.length())	return false;
		vector<vector<int>> path(s1.length() + 1, vector<int>(s2.length() + 1, -1));
		return isInterleave_(s1, 0, s2, 0, s3, path);
	}