浙江省网站备案时间,公司财务记账软件,品牌logo设计公司,广州做网站海珠信科131. 分割回文串https://leetcode.cn/problems/palindrome-partitioning/https://leetcode.cn/problems/palindrome-partitioning/
给你一个字符串 s#xff0c;请你将 s 分割成一些子串#xff0c;使每个子串都是 回文串 。返回 s 所有可能的分割方案。
示例 1#xff1a…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 16s 仅由小写英文字母组成
DFS方案1初始化一个代表分割点的01数组然后对这个数组的状态使用dfs搜索。这个方案耗时长空间复杂度也不小。具体代码如下
class Solution {
public:vectorvectorstring ans;bool cutoff[20] {false};//代表分割点的01数组bool check(string s)//判断回文串{string ss s;reverse(s.begin(),s.end());if(sss)return true;else return false;}void dfs(string s,int cur)//枚举每一个位置有在该点分割与不分割两种情况{if(cur s.size()){vectorstring 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,cur1);cutoff[cur] false;dfs(s,cur1);}vectorvectorstring partition(string s) {//为了整体代码和谐将首尾都设为分割cutoff[0] true;cutoff[s.size()] true;dfs(s,1);return ans;}
}; DFS方案2从前到后直接枚举分割点。如下图
这个方案更快些具体差别在该方案能及时排除不可能选项而不是等上一个方案把所有可能情况全列出来然后对每个依次排除。代码具体如下
class Solution {
public:vectorvectorstring ans;vectorstring temp;bool check(string s){string ss s;reverse(s.begin(),s.end());if(sss)return true;else return false;}void dfs(int startindex,const string s)//前者代表起始点{if(startindexs.size()){ans.push_back(temp);return;}for(int i startindex;is.size();i){string str s.substr(startindex,i-startindex 1);if(check(str)){temp.push_back(str);dfs(i1,s);temp.pop_back();}else continue;}}vectorvectorstring 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.1681.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 20s 仅由数字组成
思路几乎一致都是要求分割的字符串所有情况唯一不同的是这道题有些额外的条件但都很好解决具体代码如下
class Solution {
public:vectorstring ans;vectorstring temp;inline int transform(string s)//字符串转数字{int t 0;int re 0;for(int i s.size()-1;i0;i--,t){re(s[i] - 0)*pow(10,t);}return re;}bool check(string s){string ss s;reverse(s.begin(),s.end());if(sss)return true;else return false;}void dfs(int startindex,const string s)//前者代表起始点{if(temp.size()4)//很明显的剪枝return;if(startindexs.size()temp.size()4){string str;for(int i 0;itemp.size();i){for(int j 0;jtemp[i].size();j){str.push_back(temp[i][j]);}str.push_back(.);}str.pop_back();ans.push_back(str);return;}for(int i startindex;is.size();i){string str s.substr(startindex,i-startindex 1);if((str.size()2str[0] 0)||str.size()3||transform(str)255)//由题得出的筛选条件continue;temp.push_back(str);dfs(i1,s);temp.pop_back();}}vectorstring restoreIpAddresses(string s) {dfs(0,s);return ans;}
};
