给你一个字符串 s
,请你将 s
分割成一些子串,使每个子串都是
示例 1:
输入:s = "aab" 输出:[["a","a","b"],["aa","b"]]
示例 2:
输入:s = "a" 输出:[["a"]]
第一个问题是要写出判断回文串的函数,判断回文串时用到了双指针,一前一后夹击。
这个就相对简单了:
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; }
切割问题类似组合问题。
例如对于字符串abcdef:
组合问题:选取一个a之后,在bcdef中再去选取第二个,选取b之后在cdef中再选取第三个…..。
切割问题:切割一个a之后,在bcdef中再去切割第二段,切割b之后在cdef中再切割第三段…..。
所以在组合问题中用到的startIndex就是分割线的位置。
用substr选取其中的回文字符串放入path即可。
整体代码如下:
class Solution { private: 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; } vector<vector<string>> res; vector<string> path; void backtracking(const string& s, int startIndex) { if (startIndex >= s.size()) { res.push_back(path); return; } for (int i = startIndex; i < s.size(); i++) { if (isPalindrome(s, startIndex, i)) { string str = s.substr(startIndex, i - startIndex + 1); path.push_back(str); } else continue; backtracking(s, i + 1); path.pop_back(); } } public: vector<vector<string>> partition(string s) { backtracking(s, 0); return res; } };
有效 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"]
同样是要切割,只不过切割处要加上小数点。
那最后数切割产生的点怎么办呢?让path.size()-1就好了。
代码如下:
class Solution { private: vector<string> res; // 保存结果的列表 string path; // 当前路径,用于构建 IP 地址 void backtracking(const string& s, int startIndex, int points) { // 如果已经到了字符串的末尾,并且点的数量是3,说明已经找到合法的IP地址 if (startIndex == s.size() && points == 4) { res.push_back(path.substr(0, path.size() - 1)); // 去掉最后一个点,加入结果 return; } // 如果点的数量超过了3,或者索引超过了字符串长度,提前返回 if (points > 4) return; for (int i = startIndex; i < s.size() && i - startIndex < 3; i++) { string str = s.substr(startIndex, i - startIndex + 1); // 提取子串 int digit = std::stoi(str); // 转换子串为整数 // 检查是否合法的 IP 段,必须在 0-255 之间,且不能有前导0(除非是 '0' 本身) if (digit <= 255 && (str.size() == 1 || str[0] != '0')) { path += str + '.'; // 在路径中添加这个段,并加上一个点 backtracking(s, i + 1, points + 1); // 递归,点数加1 path = path.substr(0, path.size() - str.size() - 1); // 回溯,删除已经添加的段和点 } else { break; // 如果不符合条件,跳出循环 } } } public: vector<string> restoreIpAddresses(string s) { if (s.size() < 4 || s.size() > 12) return {}; // IP地址长度必须在4到12之间 backtracking(s, 0, 0); // 开始回溯,从索引0开始,点数初始为0 return res; } };
暂无评论