用回溯法解决分割回文字符串问题，时间，空间复杂度分析_回文字符串分割

题目概括：

分割回文字符串：输入一个字符串s，请将s分割成一些子串，使每个子串都是回文串。回文串是正着读和反着读都一样的字符串。

代码示例： 

#include<iostream>
#include<vector>
#include<string>
 
using namespace std;
bool isPalindrome(string s,int begin,int end){
	for(int i=begin,j=end;i<j;i++,j--){
		if(s[i]!=s[j])return false;
	}
	return true;
}
void backtrack(const string s,int begin,vector<string> &path,vector<vector<string>> &result){
	if(begin==s.length()){
		result.push_back(path);
		return;
	}
	else{
		for(int i=begin;i<s.length();i++){
			if(isPalindrome(s,begin,i)){
				string str=s.substr(begin,i-begin+1);
				path.push_back(str);
			}
			else{
				continue;
			}
			backtrack(s,i+1,path,result);
			path.pop_back();
		}
	}
}
int main(){
	vector<string> path;
	vector<vector<string>> result;
	string text;
	cout<<"输入: s = ";
	cin>>text;
	backtrack(text,0,path,result);
	cout<<"输出: ";
	cout<<'[';
	for(auto &a:result){
		cout<<'[';
		for(auto &b:a){
			cout<<"\""<<b<<"\"";
			if(&b!=&a.back())cout<<',';
		}
		cout<<']';
		if(&a!=&result.back())cout<<',';
	}
	cout<<']';
	cout<<endl;
}

回溯法是比较难理解的一种算法，可以将其理解成一颗树的后序遍历。

在我的代码中包含了三个函数，分别为:主函数main，判断是否为回文字符串isPalindrome，回溯寻找回文字符串backtrack。

主函数与isPalindrome都比较好理解，一个是负责控制输入与输出结果，一个是负责判断字符串是否回文。这里就不使用过多语言赘述。

backtrack函数中需传入4个元素：

String s：我们输入的字符串，在回溯中不会改变；

int begin：需要从s的哪个位置开始判断；

vector<string> &path：用来储存一种回文字符串的分割情况；

 vector<vector<string>> &result：用来储存所有回文字符串的分割情况，也就是结果（只有触底的path才有资格进入结果中）；

首先先将代码的逻辑表示出来：

如果触底了（s遍历完了），也就是begin==s.length()，就需要回溯，并将这次的分割情况放入结果中；

如果是回文子串，就继续深入，遍历剩下的字符（backtrack(s,i+1,path,result);）；

如果不是回文子串，就访问兄弟节点（continue）；

如果没有兄弟节点或兄弟节点没有了（i=s.length()）也同样回溯（参考后续遍历）；

回溯图示：

这里是我对回溯过程的认知图，有错误可以指出：

尽力了，应该可以看得懂 ：）

按照我的箭头一步步看下来。

在这里我们可以看到这个算法和后序遍历结构类似，而且每层的元素数量是相同的，因为在每一次循环中都要执行一次push与pop的操作。（continue会跳过这次循环，所以不会执行pop，所以不存在只push不pop的情况）

这个代码的核心，其实就是在模拟一种“尝试与错误”的过程。每次尝试一个分割方案，如果走得通，就继续往下走；走不通了，就尝试隔壁的路，如果隔壁也行不通就回到上一个路口。通过这样反复的“试探”，就能找到所有合理的分割方案。

时间，空间复杂度分析：

为了测试回溯法的时间复杂度和空间复杂度，我们可以设计以下测试数据集：

随机生成不同长度的字符串s，长度从0到200，每隔10增加一次，共20组数据；

对于每组数据，记录回溯法的运行时间和占用的内存空间；

这里是测试时的代码：

#include<iostream>
#include<vector>
#include<string>
#include<windows.h>
#pragma comment( lib,"winmm.lib" )
 
using namespace std;
bool isPalindrome(string s,int begin,int end){
	for(int i=begin,j=end;i<j;i++,j--){
		if(s[i]!=s[j])return false;
	}
	return true;
}
void backtrack(const string s,int begin,vector<string> &path,vector<vector<string>> &result){
	if(begin==s.length()){
		result.push_back(path);
		return;
	}
	else{
		for(int i=begin;i<s.length();i++){
			if(isPalindrome(s,begin,i)){
				string str=s.substr(begin,i-begin+1);
				path.push_back(str);
			}
			else{
				continue;
			}
			backtrack(s,i+1,path,result);
			path.pop_back();
		}
	}
}
string randomString(int n) {
	string s;
	char chars[] = "abcdefghijklmnopqrstuvwxyz";
	int len = sizeof(chars) - 1;
	srand(time(NULL));
	for (int i = 0; i < n; i++) {
		int index = rand() % len;
		s += chars[index];
	}
	return s;
}
int main(){
	vector<string> path;
	vector<vector<string>> result;
	string text;
	LARGE_INTEGER t1, t2, tc;
	long int space;
	for (int n = 0; n <= 200; n += 10) { 
		text = randomString(n);
		cout<<"字符串长度"<<n<<endl;
		QueryPerformanceFrequency(&tc);
		QueryPerformanceCounter(&t1);
		backtrack(text, 0, path, result);
		QueryPerformanceCounter(&t2);
		printf("时间占用:%f", (t2.QuadPart - t1.QuadPart)*1.0 / tc.QuadPart);
		space=sizeof(result)+((sizeof(path)+(path.capacity()*sizeof(string)))*result.capacity());
		cout <<"	||	空间占用"<< space << endl;
		path.clear();
		result.clear();
	}
}

这里使用的是capacity而不是使用sizeof是因为vector是一个动态数组，所以它会预留一部分的空间，所以所占用的实际空间要大于里面元素所占用的空间。

vector还带有三个指针：

一个是内存的开始，

一个是内存的结束，

还有一个是预分配内存的结束;

这三个指针我使用sizeof直接计算，指针本质上是存储一个内存地址，而内存地址的大小是由处理器的地址总线宽度决定的，所以一般不会变化。

记录数据：

由于数据的差异所以实验的结果随机性较高 ，所以我将其画成图标以便观察

时间复杂度分析： 

回溯法的时间复杂度的渐进分析如下：

        设字符串s的长度为n，最坏的情况是s中没有任何回文串，那么回溯法需要尝试所有的2^(n-1)种分割方案，每种方案需要O(n)的时间来判断是否是回文串，因此最坏情况下（全是同一个字符）的时间复杂度是O(n*2^(n-1))；
        最好的情况是s本身就是一个回文串，且就只有这一串回文串，那么这棵树就只有一个分支，只需要一次判断，时间复杂度是O(n)；
        平均情况下，回溯法的时间复杂度取决于s中回文串的分布，一般来说，回溯法的时间复杂度是指数级的，即O(2^n)。

空间复杂度分析： 

回溯法的空间复杂度的渐进分析如下：

设字符串s的长度为n，回溯法需要使用一个字符串向量path来存储当前的分割方案，一个字符串向量的向量result来存储最终的所有分割方案，以及一个整数begin来表示当前的起始位置；

path的长度为n，因此path的空间复杂度是O(n)；

result的长度最多为2^(n-1)，每个元素的长度最多为n(path)，因此result的空间复杂度是O(n*2^(n-1))；

(应该有更多，因为vector数组会预设空间来保证性能，如果到达预设内存会继续分配内存，根据编译器会有不同的情况，比如vs2010会再次分配原容量一半的容量,所以空间占用应呈现阶梯状)

begin的空间复杂度是O(1)；

Path与result每个还带三个指针，时间复杂度为O(1)；

因此，回溯法的总空间复杂度是O(n*2^(n-1))。

如果有错误欢迎指出