算法刷题心得：动态规划 scramble-string

牛客网->在线编程->letcode->scramble-string

Given a string s1, we may represent it as a binary tree by partitioning it to two non-empty substrings recursively.Below is one possible representation ofs1 ="great":

To scramble the string, we may choose any non-leaf node and swap its two children.For example, if we choose the node"gr"and swap its two children, it produces a scrambled string"rgeat".

We say that"rgeat"is a scrambled string of"great".Similarly, if we continue to swap the children of nodes"eat"and"at", it produces a scrambled string"rgtae".

We say that"rgtae"is a scrambled string of"great".Given two stringss1 ands2 of the same length, determine if s2 is a scrambled string ofs1.

刚开始拿到题目并没有用到DP，做了一个全局搜索，结果超时了。也先写一下我的思路，再贴一下参考别人的DP大神代码。我的思路：先用数字表示字符串，方便讲解，

定义：

1、切点，要将一个字符串变成两个非空二叉树，则需要将在字符串中间插空切下去，比如str1=“1234”就有12之间、23之间、34之间三个切点；后面根据切点的从左到右的顺序命名为：cut[i]；

示例一：str1=“1234”、str2=“3142”；若想将str2经过变换成为str1，二叉树第一层分支点可以有三种切点情况；（判断可行情况是左右子树是否交叉，因为左右子树元素之间是不会交叉的，只是左右子树交换）

（其实已经构造出了最优子结构，动态规划的核心。但是由于对这种不是一维二维的动态规划见得少，没有做出来。。）我的代码就是这种深搜，最后超时。不知道代码有没有什么BUG，自己测了一些还没测出问题

map<char,vector<int> > tab,rtab;
map<char,int> flag;
string ss;
void clear(map<char,int> &tmp){
	map<char,int>::iterator it;
	for(it=tmp.begin(); it!=tmp.end(); it++)
		it->second = 0;
}
//功能：返回从左向右搜索，下一个可能切点的位置
//形参：s2是str2二叉树的某一个子树，left、right为在原str2的左右界限，pos为开始搜索位置
int c_find(const string &s2,int left,int right,int pos){
	if(pos>right)
		return right;
	int i=left, j=pos;
	clear(flag);
	do{
		int tmp;
		do{
			tmp = tab[s2[i-left]][flag[s2[i-left]]];
			if(tmp==-1 || tmp>=right)
				return right;
		}while(flag[s2[i-left]]++,tmp<left);
		j = max(j, tmp);
		flag[s2[i-left]]++;
	}while(i++<j);
	return --i;
}
//功能：返回从右向左搜索，下一个可能切点的位置
//形参：s2是str2二叉树的某一个子树，left、right为在原str2的左右界限，pos为开始搜索位置
int c_rfind(const string &s2,int left,int right,int pos){
	if(pos<left)
		return left;
	int i=left, j=pos;
	clear(flag);
	do{
		int tmp;
		do{
			tmp = rtab[s2[i-left]][flag[s2[i-left]]];
			if(tmp==-1 || tmp<=left)
				return left;
		}while(flag[s2[i-left]]++,tmp>right);
		j = min(j, tmp);
		//flag[s2[i-left]]++;
	}while(i++<(right-j));
	return j;
}
bool scramble_judge(const string &s1,const string &s2,int left,int right){
	//cout<<s2<<endl;
	if(left == right && ss[left]==s2[0])
		return true;
	if(right-left == 1){
		if((ss[left]==s2[0] && ss[right]==s2[1]) || (ss[left]==s2[1] && ss[right]==s2[0]))
			return true;
		else
			return false;
	}
	int tmp=-1,rtmp=0x3f3f3f3f;
	for(int i=left;i<right;i=min(tmp+1,left+right-rtmp+1)){
		tmp = c_find(s2, left, right, max(i,tmp+1));//左左右右查询
		/*if(tmp == right)
			return false;*/
		if(tmp<right && ( scramble_judge(s1,s2.substr(0,tmp-left+1),left,tmp) && scramble_judge(s1,s2.substr(tmp-left+1),tmp+1,right) ) ){
			return true;
		}else{
			rtmp = c_rfind(s2, left, right, min(rtmp-1,right+left-i));//左右左右查询
			if(rtmp <= left)
				return false;
			if( scramble_judge(s1,s2.substr(0,right-rtmp+1),rtmp,right) && scramble_judge(s1,s2.substr(right-rtmp+1),left,rtmp-1) )
				return true;
		}
	}
	return false;
}
bool isScramble(string s1, string s2) {
    int len1=s1.size(), len2=s2.size();
	if(len1 != len2)
		return false;
	if(0 == len1)
		return true;
	if(len1==1){
		return (s1[0] == s2[0]);
	}
	//下面到return建表是想优化一下下个切点位置；根据前面数字字符串那里讲解不能交叉的原理
	set<char> char_set; 
	for(int i=0; i<len1; i++){
		char_set.insert(s2[i]);
	}
	set<char>::iterator it;
	for(it=char_set.begin(); it!=char_set.end(); it++){
		flag[*it] = 0;
		tab[*it] = vector<int>(len1+1,-1);
		int j=0;
		for(int i=0; i<len1;i++){
			if(*it == s1[i])
				(tab[*it])[j++] = i;//str2某个字符在str1中出现的位置（存储顺序为递增）
		}
		if(j == 0)
			return false;
	}
	for(it=char_set.begin(); it!=char_set.end(); it++){
		rtab[*it] = vector<int>(len1+1,-1);
		int j=0,k=-1;
		while((tab[*it])[++k] != -1);
		while(k){
			(rtab[*it])[j++] = (tab[*it])[--k];//str2某个字符在str1中出现的位置（存储顺序为递减）
		}
	}
	return scramble_judge(s2, s2, 0, len1-1);
}

别人的动态规划算法：dp[k][i][j]表示str1从i开始长度为k，与str2从j开始长度为k的子串是否为scramble-string

bool isScramble(string s1, string s2) {
	int len1=s1.size(), len2=s2.size();
	if(len1 != len2)
		return false;
	//相当于 bool dp[len1][len1][len1];
	vector<vector<vector<bool> > > dp(len1, vector<vector<bool>>(len1,vector<bool>(len1,false)) );
	//初始化数组，子串长度为一时，只要相等就是
	for(int i=0; i<len1; i++){
		for(int j=0; j<len1; j++){
			if(s1[i] == s2[j])
				dp[0][i][j] = true;
		}
	}
	for(int k=1;k<len1; k++){
		for(int i=0; i<len1-k ;i++){
			for(int j=0; j<len1-k; j++){
				if(false == dp[k][i][j]){
					for(int q=0; q<k; q++){
						if( (dp[q][i][j] && dp[k-q-1][i+q+1][j+q+1]) || (dp[q][i][j+k-q] && dp[k-q-1][i+q+1][j]) )
							dp[k][i][j] = true;
					}
				}
			}
		}
	}
	return dp[len1-1][0][0];
}