目录
131.分割回文串
93.复原IP地址
131.分割回文串
131. 分割回文串
中等
给你一个字符串 s，请你将 s 分割成一些子串，使每个子串都是 回文串 。返回 s 所有可能的分割方案。
回文串 是正着读和反着读都一样的字符串。
示例 1：
输入：s = "aab" 输出：[["a","a","b"],["aa","b"]]
示例 2：
输入：s = "a" 输出：[["a"]]
提示：
1 <= s.length <= 16s仅由小写英文字母组成
其实切割问题类似组合问题。
例如对于字符串abcdef：
- 组合问题：选取一个a之后，在bcdef中再去选取第二个，选取b之后在cdef中再选取第三个.....。
- 切割问题：切割一个a之后，在bcdef中再去切割第二段，切割b之后在cdef中再切割第三段.....。
解读题意：每存在一种方式可将字符串分割为回文子串时，就将分割好的回文子串存到一个List集合中，再存入List结果集合中
// Solution类，包含了分割字符串为回文子串的方法
class Solution { // 用于存储所有可能的分割方案，每个方案是一个字符串列表 List<List<String>> lists = new ArrayList<>(); // 用于临时存储当前分割方案的回文子串 List<String> substring = new ArrayList<>(); // public方法，接收一个字符串s，返回所有可能的回文子串分割方案 public List<List<String>> partition(String s) { // 调用回溯方法开始分割字符串 backTracking(s, 0); // 返回所有分割方案 return lists; } // 私有方法，使用回溯法分割字符串 private void backTracking(String s, int startIndex) { // 如果起始位置超过了字符串的长度，说明已经找到了一个完整的分割方案 if (startIndex == s.length()) { // 将当前方案添加到结果列表中（注意这里要添加deque的副本） lists.add(new ArrayList<>(substring)); return; } // 遍历从起始位置到字符串末尾的每个位置 for (int i = startIndex; i < s.length(); i++) { // 检查从startIndex到i的子串是否是回文的 if (isPalindrome(s, startIndex, i)) { // 如果是回文子串，则添加到当前方案中 String str = s.substring(startIndex, i + 1); substring.add(str); } else { // 如果不是回文子串，则跳过当前位置，继续向后检查 continue; } // 回溯，将起始位置后移一位，继续寻找下一个回文子串 backTracking(s, i + 1); // 回溯，移除当前方案中的最后一个回文子串，尝试其他可能性 substring.removeLast(); } } // 私有辅助方法，用于判断一个子串是否是回文的 private boolean isPalindrome(String s, int startIndex, int end) { // 使用双指针法，一个指针从起始位置开始，另一个指针从结束位置开始 for (int i = startIndex, j = end; i < j; i++, j--) { // 如果两个指针指向的字符不相等，则子串不是回文的 if (s.charAt(i) != s.charAt(j)) { return false; } } // 如果所有字符都相等，则子串是回文的 return true; }
}93.复原IP地址
93. 复原 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 地址。
给定一个只包含数字的字符串 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 { List<String> result = new ArrayList<>(); // 用于存放所有可能的IP地址 StringBuilder builder = new StringBuilder(); // 用于构建当前的IP地址 public List<String> restoreIpAddresses(String s) { backtracking(s, 0, 0); // 从字符串的开头开始回溯，还没有任何段被选择 return result; // 返回所有可能的IP地址列表 } public void backtracking(String s, int begin, int numCount) { // 如果已经遍历完整个字符串，并且已经选择了4个段，说明找到了一个可能的IP地址 if (begin == s.length() && numCount == 4) { result.add(builder.toString()); return; } // 如果已经遍历完整个字符串，或者已经选择了4个段，但字符串还没有遍历完，说明当前路径不可能构成IP地址 if (begin == s.length() || numCount == 4) { return; } // 遍历可能的段结束位置 for (int i = begin; i < s.length(); i++) { // 检查当前子串是否可以作为一个IP地址的段 if (isvalid(s, begin, i)) { // 将当前段添加到构建器中 builder.append(s.substring(begin, i + 1)); numCount++; // 已选段数加一 // 如果当前选择的段数小于4，说明还需要继续选择段，因此添加一个点作为分隔符 if (numCount < 4) { builder.append("."); } // 继续回溯，选择下一个段 backtracking(s, i + 1, numCount); // 回溯，删除当前段以及分隔的点（如果存在） // 注意：删除的是当前段的最后一个字符到构建器末尾的所有字符，即整个段和可能存在的点 //从开始位置+加入的点的位置开始builder.delete(begin + numCount - 1, builder.length()); numCount--; // 已选段数减一 } else { // 如果当前子串不能作为一个IP地址的段，则跳出循环，尝试下一个可能的开始位置 //如果不是一段有几种情况，长度大于一且0开头，数字大于255，长度大于3，往下遍历没有意义 break; } } } //这里的begin和end是左闭右闭的区间 public boolean isvalid(String s, int begin, int end) { // 如果开始位置大于结束位置，说明子串为空，不是有效的段 if (begin > end) { return false; } // 如果子串表示的整数大于255，不是有效的段 if (Integer.parseInt(s.substring(begin, end + 1)) > 255) { return false; } // 如果子串长度大于3，不是有效的段（IP地址段最多3位数字） if (end - begin + 1 > 3) { return false; } // 如果子串以0开头且长度大于1（除了单个0的情况），不是有效的段 if (s.charAt(begin) == '0' && end - begin > 0) { return false; } // 如果以上条件都不满足，说明子串是一个有效的段 return true; }
}
