Leetcode 131 分割回文串(纯DFS)

131. 分割回文串https://leetcode.cn/problems/palindrome-partitioning/https://leetcode.cn/problems/palindrome-partitioning/

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

示例 1：

输入：s = "aab"
输出：[["a","a","b"],["aa","b"]]

示例 2：

输入：s = "a"
输出：[["a"]]

提示：

• 1 <= s.length <= 16
• s 仅由小写英文字母组成

DFS方案1：初始化一个代表分割点的01数组，然后对这个数组的状态使用dfs搜索。这个方案耗时长，空间复杂度也不小。具体代码如下：

class Solution {
public:vector<vector<string>> ans;bool cutoff[20] = {false};//代表分割点的01数组bool check(string s)//判断回文串{string ss = s;reverse(s.begin(),s.end());if(ss==s)return true;else return false;}void dfs(string s,int cur)//枚举每一个位置，有在该点分割与不分割两种情况{if(cur == s.size()){vector<string> temp;int i = 0;while(true){string t;t.push_back(s[i]);i++;while(!cutoff[i]){t.push_back(s[i]);i++;}if(!check(t))return;else temp.push_back(t);if (i >= s.size())break;}ans.push_back(temp);return;}cutoff[cur] = true;dfs(s,cur+1);cutoff[cur] = false;dfs(s,cur+1);}vector<vector<string>> partition(string s) {//为了整体代码和谐，将首尾都设为分割cutoff[0] = true;cutoff[s.size()] = true;dfs(s,1);return ans;}
};

DFS方案2：从前到后直接枚举分割点。如下图：

这个方案更快些，具体差别在该方案能及时排除不可能选项，而不是等上一个方案把所有可能情况全列出来然后对每个依次排除。代码具体如下：

class Solution {
public:vector<vector<string>> ans;vector<string> temp;bool check(string s){string ss = s;reverse(s.begin(),s.end());if(ss==s)return true;else return false;}void dfs(int startindex,const string s)//前者代表起始点{if(startindex==s.size()){ans.push_back(temp);return;}for(int i = startindex;i<s.size();++i){string str = s.substr(startindex,i-startindex + 1);if(check(str)){temp.push_back(str);dfs(i+1,s);temp.pop_back();}else continue;}}vector<vector<string>> partition(string s) {dfs(0,s);return ans;}
};

顺便说一道几乎一样的题：

93. 复原 IP 地址https://leetcode.cn/problems/restore-ip-addresses/

有效 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"]

提示：

• 1 <= s.length <= 20
• s 仅由数字组成

思路几乎一致，都是要求分割的字符串所有情况，唯一不同的是这道题有些额外的条件，但都很好解决，具体代码如下：

class Solution {
public:vector<string> ans;vector<string> temp;inline int transform(string s)//字符串转数字{int t = 0;int re = 0;for(int i = s.size()-1;i>=0;i--,t++){re+=(s[i] - '0')*pow(10,t);}return re;}bool check(string s){string ss = s;reverse(s.begin(),s.end());if(ss==s)return true;else return false;}void dfs(int startindex,const string s)//前者代表起始点{if(temp.size()>4)//很明显的剪枝return;if(startindex==s.size()&&temp.size()==4){string str;for(int i = 0;i<temp.size();++i){for(int j = 0;j<temp[i].size();++j){str.push_back(temp[i][j]);}str.push_back('.');}str.pop_back();ans.push_back(str);return;}for(int i = startindex;i<s.size();++i){string str = s.substr(startindex,i-startindex + 1);if((str.size()>=2&&str[0] == '0')||str.size()>3||transform(str)>255)//由题得出的筛选条件continue;temp.push_back(str);dfs(i+1,s);temp.pop_back();}}vector<string> restoreIpAddresses(string s) {dfs(0,s);return ans;}
};