leetcode 131
问题描述：
给你一个字符串 s，请你将 s 分割成一些子串，使每个子串都是 回文串 。返回 s 所有可能的分割方案。
回文串 是正着读和反着读都一样的字符串。
示例 1：
输入：s = "aab"
输出：[["a","a","b"],["aa","b"]]
示例 2：
输入：s = "a"
输出：[["a"]]
思路
由于也是将字符串中的a拿出来，然后再与字符串当中的字母进行组合，所以其实也相当于组合问题，只不过，还多了一个判断是否为回文子串的问题。
所以可以考虑用回溯三部曲来分析做题。
返回值与参数
全局变量 result与path分别存储全部的结果与每次的结果，另外还可以添加一个参数startIndex，记录遍历的位置，也就是初始的位置，方便往下递归时候调用。
vector<vector<string>> result;//存储全部的结果
vector<string> path;
void backtracking(const string& s,int starIndex )
递归函数与终止条件
如果选取的位置大于或者等于s字符串的大小，那么就可以判断为取到合适的回文字符串；
if(startIndex >= s.size()){
result.push_back(path);
return;
}
遍历
for依然适用于横向遍历，递归适合往下遍历；这道题当中，还有一个问题就是判断所取得的字符串是否为回文。
for(int i = starIndex;i < s.size();i++)
{
if(isPalindrome(s,starIndex,i)){
//判断是否是回文子串,获取[startIndex]在s中的子串
string str = s.substr(starIndex,i - starIndex + 1);
path.push_back(str);
}
else{
continue;
}
backtracking(s,i+1); //寻找i+1的起始位置的子串
path.pop_back(); //回溯过程，弹出本次已经处理的子串
}
判断回文的函数：
bool isPalindrome(const string& s,int start,int end)
{
for(int i = start, j = end;i < j;i++,j--)
{
if(s[i] != s[j])
{
return false;
}
}
return true;
}
所有代码
class Solution {
private:
vector<vector<string>> result;//存储全部的结果
vector<string> path;
void backtracking(const string& s,int starIndex ){
if(starIndex >= s.size())
{
//递归终止条件，是否大于该大小，如果大于就说明获得了一个数组
result.push_back(path);
return;
}
for(int i = starIndex;i < s.size();i++)
{
if(isPalindrome(s,starIndex,i)){
//判断是否是回文子串
string str = s.substr(starIndex,i - starIndex + 1);
path.push_back(str);
}
else{
continue;
}
backtracking(s,i+1);
path.pop_back();
}
}
bool isPalindrome(const string& s,int start,int end)
{
for(int i = start, j = end;i < j;i++,j--)
{
if(s[i] != s[j])
{
return false;
}
}
return true;
}
public:
vector<vector<string>> partition(string s) {
result.clear();
path.clear();
backtracking(s,0);
return result;
}
};
小结
本题难点：
- 判断这个为回溯问题：将分割问题抽象为回溯
- 判断的依据：题目字眼中有分割，重新组合，需要for循环多次遍历的
- 本题当中，还需要考虑的一个问题就是判断字符串回文
leetcode 93
题目描述：
有效 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 地址。
给定一个只包含数字的字符串 s ，用以表示一个 IP 地址，返回所有可能的有效 IP 地址，这些地址可以通过在 s 中插入 '.' 来形成。你 不能 重新排序或删除 s 中的任何数字。你可以按 任何 顺序返回答案。
示例 1：
输入：s = "25525511135"
输出：["255.255.11.135","255.255.111.35"]
示例 2：
输入：s = "0000"
输出：["0.0.0.0"]
示例 3：
输入：s = "101023"
输出：["1.0.10.23","1.0.102.3","10.1.0.23","10.10.2.3","101.0.2.3"]
思路
切割问题，可以直接套用回溯三部曲进行分析
参数与返回值
本题主要就是分割数字段，除了记录下一层递归分割的起始位置的参数startIndex,还需要一个记录分段点数值pointNum;
vector<string> result;
//startIndex记录起始值，pointNum记录点的数量
void backtracking(string& s,int startIndex,int pointNum)
终止条件与递归函数
因为要分4段，所有就需要切三次，所以点数值保证在3就可以终止了，其次就是保证该字段的有效性。
if(pointNum == 3)
{
if(isValid(s, startIndex, s.size()-1))//需要添加判断字段有效性的函数
{
result.push_back(s);
}
return;
}
遍历
for 横向遍历，递归函数向下遍历；
for (int i = startIndex; i < s.size();i++)
{
if(isValid(s,startIndex,i))
{
s.insert(s.begin()+i+1,'.');
pointNum++;
backtracking(s,i+2,pointNum);
pointNum--;
s.erase(s.begin() + i + 1);
}else break;
}
判断网络段的有效性，有三点：
- 段位不能以0开头
- 段位里有非正整数字符不合法
- 不能大于255
所以函数为：
bool isValid(const string& s,int start,int end)
{
if(start > end)
{
return false;
}
if(s[start]=='0' && start != end)
{
return false;
}
int num = 0;
for(int i = start;i <= end;i++){
if (s[i] > '9' || s[i] < '0')
{
return false;
}
num = num*10 + (s[i] - '0');
if(num > 255)
{
return false;
}
}
return true;
}
全部代码
class Solution {
private:
vector<string> result;
//startIndex记录起始值，pointNum记录点的数量
void backtracking(string& s,int startIndex,int pointNum)
{
if(pointNum == 3)
{
if(isValid(s, startIndex, s.size()-1))
{
result.push_back(s);
}
return;
}
for (int i = startIndex; i < s.size();i++)
{
if(isValid(s,startIndex,i))
{
s.insert(s.begin()+i+1,'.');
pointNum++;
backtracking(s,i+2,pointNum);
pointNum--;
s.erase(s.begin() + i + 1);
}else break;
}
}
bool isValid(const string& s,int start,int end)
{
if(start > end)
{
return false;
}
if(s[start]=='0' && start != end)
{
return false;
}
int num = 0;
for(int i = start;i <= end;i++){
if (s[i] > '9' || s[i] < '0')
{
return false;
}
num = num*10 + (s[i] - '0');
if(num > 255)
{
return false;
}
}
return true;
}
public:
vector<string> restoreIpAddresses(string s) {
result.clear();
if (s.size() > 12) return result;
backtracking(s,0,0);
return result;
}
};
本题小结
难点：
- 切割问题转化为回溯算法思考
- 对于题设当中的关键参数，能不能转化为代码
- 本题的判断段位值的有效性