回溯法解决分割问题

1 题目描述

给定一个字符串 s，将 s 分割成一些子串，使每个子串都是回文串。返回 s 所有可能的分割方案。

示例:

输入:“aab”

输出: [ [“aa”,“b”], [“a”,“a”,“b”] ]

题目来源：131. 分割回文串 - 力扣（LeetCode）

2 求解思路

2.1实例分析

  根据题目来看，解题过程可大致分为两步

1. 判断所有子串是否为回文串；
2. 递归+回溯，遍历每一个子区间，当走到字符串尾部的时候输出一个可行方案，回溯并寻找下一个可行方案

例：切割a a b

 

 

2.2算法实现

首先读入字符串，进入dfs函数，起始位置从第一个字母开始，通过for循环和回溯遍历不同长度的子串，利用双指针算法，判断是否为回文串，符合则加入，当到达尾部时，则为一个答案，输出.

2.3伪代码

  (1)判断回文串的函数

算法一：

bool is_str(string s)
{
	string s1 = s;
	reverse(s1.begin(), s1.end());
	if (s == s1)return true;
	else return false;
}

 算法二:

memset(f, true, sizeof f);
for (int i = 0; i < s.size(); i++)
	for (int j = i + 1; j < s.size(); j++)
	{
		f[i][j] = (s[i] == s[j]) && f[i + 1][j - 1];
	}

1. dfs回溯函数

算法一：

 void dfs(int index)
{
	if (index >= len)
	{
		for (int i = 1; i <= x; i++) cout << ans[i] << " ";
		cout << endl;
		return;
	}
	for (int i = index; i < len; i++)
	{
		if (ishw(index, i))
		{
			string str = s.substr(index, i - index + 1);
			ans[++x] = str;
			//cout<<ans[x]<<" ";
		}
		else continue;//不是回文，则跳过，不能省略哦 
		dfs(i + 1);
		x--;
	}
}

算法二：

void dfs(const string& s, int i)
{
	if (i == n)
	{
		for (auto t : v)
			cout << t << " ";
		cout << endl;
		return;
	}
 
	for (int j = i; j < s.size(); j++)
	{
		if (f[i][j])
		{
			cnt++;
			v.push_back(s.substr(i, j - i + 1));
			dfs(s, j + 1);
			v.pop_back();
		}
	}
}

3 源代码

算法一：双指针判回文+回溯

#include<bits/stdc++.h>
using namespace std;
string ans[105];
string s;
int len;
int x = 0;
bool ishw(int start, int end)//双指针判定回文
{
	int i = start, j = end;
	for (; i < j; i++, j--)
	{
		if (s[i] != s[j]) return false;
	}
	return true;
}
void dfs(int index)
{
	if (index >= len)
	{
		for (int i = 1; i <= x; i++) cout << ans[i] << " ";
		cout << endl;
		return;
	}
	for (int i = index; i < len; i++)
	{
		if (ishw(index, i))
		{
			string str = s.substr(index, i - index + 1);
			ans[++x] = str;
			//cout<<ans[x]<<" ";
		}
		else continue;//不是回文，则跳过，不能省略哦 
		dfs(i + 1);
		x--;
	}
}
int main()
{
	cin >> s;
	len = s.size();
	//cout<<ishw(0,len-1);
	dfs(0);
 
	return 0;
}

算法二：动态规划判回文+回溯

#include<iostream>
#include<algorithm>
#include<vector>
#include<cstring>
using namespace std;
string s;
int n; int cnt = 1;
bool f[1001][1001];
vector<string>v;
 
void dfs(const string& s, int i)
{
	if (i == n)
	{
		for (auto t : v)
			cout << t << " ";
		cout << endl;
		return;
	}
 
	for (int j = i; j < s.size(); j++)
	{
		if (f[i][j])
		{
			cnt++;
			v.push_back(s.substr(i, j - i + 1));
			dfs(s, j + 1);
			v.pop_back();
		}
	}
}
 
signed main()
{
	cin >> s;
	n = s.size();
	memset(f, true, sizeof f);
	for (int i = 0; i < s.size(); i++)
		for (int j = i + 1; j < s.size(); j++)
		{
			f[i][j] = (s[i] == s[j]) && f[i + 1][j - 1];
		}
	dfs(s, 0);
 
	return 0;
}

代码说明：

在动态规划求回文子串时，此处memset，将f中的所有元素初始化为true，因为在下方的dp中，判断f[i][j]是否为回文子串的条件是，头尾字符相等且中间得字符串为回文串，由于起始时判断的是长度为2的字符串，那么只需要第一个判断条件即可，后面的条件结果必然为true，故应有初始化使得f[i+1][i]为true，并且单个字符必然为true，故还应使f[i][i]为true，若使用memset使得所有状态开始都为true，到不是回文串的情况，会被赋为false，最终效果，两者等同.

4.小结

  分割回文子串涉及了回文串判别和搜索两大知识，for循环走宽度，递归走深度，在处理递归函数时，需要认真的进行思考，得出正确的递归式以及跳出条件。如果使用dp来判断回文子串，需要深入理解f数组的含义，以及初始化的方法以及范围。

进阶问题

1 问题描述

给定一个只包含数字的字符串，用以表示一个 IP 地址，返回所有可能从 s 获得的 有效 IP 地址 。你可以按任何顺序返回答案。有效 IP 地址 正好由四个整数（每个整数位于 0 到 255 之间组成，且不能含有前导 0），整数之间用 ‘.’ 分隔。

例如：“0.1.2.201” 和 “192.168.1.1” 是 有效 IP 地址，但是 “0.011.255.245”、“192.168.1.312” 和 “192.168@1.1” 是 无效 IP 地址。

输入：

    25525511135

输出：

"255.255.11.135","255.255.111.35

题目来源：93. 复原 IP 地址 - 力扣（LeetCode）

 

2 解题思路

在仔细阅读题目后，可以发现此题与上一道分割回文串的思路高度相似，可以采用类似的思路进行分析，可以分为两大步来求解

判断每段子IP的大小+递归-回溯

2.1实例分析

例子：25525511135

 

2.2 算法实现

(1)判断每段子IP的大小。在规定中，每一段子串的大小不能超过255，所以当子串的长度小于3时，结果一定是成立的，当长度等于3时，使用等式对大小进行判断，符合条件的串插入，当长度大于3时，则一定不符合条件，continue，同时，第一个字符是0的子串跳过。

(2)递归+回溯，遍历每一个子区间，当走到字符串尾部的时候输出一个可行方案，回溯并寻找下一个可行方案，由于IP地址只有四位，所以不满足四位IP的方案直接return。

3 源代码 

#include<iostream>
#include<cstring>
#include<cmath>
#include<vector>
#include<algorithm>
using namespace std;
string s;
vector<string>v;
 
void dfs(const string& s, int i)
{
	
	if (i == s.size())
	{
		if (v.size() != 4)return;
		for (int i=0;i<v.size();i++)
		{
			cout << v[i];
			if (i !=v.size()-1)cout << '.';
		}
		puts(" ");
		return;
	}
 
	for (int j = i; j < s.size(); j++)
	{
		if (s[i] == '0'&&i!=j)continue;
		if (j - i <=2)
		{
			if (j - i == 2)
			{
				if (((s[i] - '0') * 100 + (s[i + 1] - '0') * 10 + (s[i + 2] - '0'))>255)
				{
					continue;
				}
			}
			v.push_back(s.substr(i, j - i + 1));
			dfs(s, j + 1);
			v.pop_back();
		}
	}
}
 
signed main()
{
	ios::sync_with_stdio(false);
	cin >> s;
	if (s.size() > 12)return 0;
	dfs(s, 0);
}

代码说明

1. 当输入字符串长度大于12时，直接跳出，不存在答案，因为单个子串的数值大小不大于255，即不超过三位数，而有四个子串，故长度不超过12.
2. 在递归函数中，遍历方式与上题完全一致，当子串长度小于等于2时，直接插入数组，等于3时，判断是否小于255。当走到字符串尾部时，输出一种情况

4 小结

  此题与上一道分割回文子串高度相似，具有练习的意义。