Letcode 131.
给你一个字符串 s
,请你将 s
分割成一些子串,使每个子串都是 回文串 。返回 s
所有可能的分割方案。
回文串 是正着读和反着读都一样的字符串。
示例 1:
输入:s = "aab" 输出:[["a","a","b"],["aa","b"]]
示例 2:
输入:s = "a" 输出:[["a"]]
提示:
1 <= s.length <= 16
s
仅由小写英文字母组成
回溯的模板:
参数(一维数组存单次满足条件,二维数组存最终条件,startIndex存开始位置(不允许重复)),终止条件
遍历所有(外循环)
内部逻辑(回溯)
for(....){
条件满足(回文判断)
path加入
backtracking
}
这题最重要的一点就是想清楚切割线怎么表达,startIndex就是切割线的位置。 以及判断是否回文的切割范围怎么表达。 (startIndex,i)就是切割的判断范围。其他的方面和其他的回溯题没有什么区别
class Solution { List<List<String>> lists = new ArrayList<>(); Deque<String> deque = new LinkedList<>(); public List<List<String>> partition(String s) { backTracking(s, 0); return lists; } private void backTracking(String s, int startIndex) { //如果起始位置大于s的大小,说明找到了一组分割方案 if (startIndex >= s.length()) { lists.add(new ArrayList(deque)); return; } for (int i = startIndex; i < s.length(); i++) { //如果是回文子串,则记录 if (isPalindrome(s, startIndex, i)) { String str = s.substring(startIndex, i + 1); deque.addLast(str); } else { continue; } //起始位置后移,保证不重复 backTracking(s, i + 1); deque.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地址
有效 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
仅由数字组成
思路:
主要是要注意对于IP地址的合法性判断问题。分割问题的变种,对于分割的范围判断,对于startIndex的计算需要加上 .
终止的条件写法:
if (pointNum == 3) { // 逗点数量为3时,分隔结束 // 判断第四段子字符串是否合法,如果合法就放进result中 if (isValid(s, startIndex, s.size() - 1)) { result.push_back(s); } return; }
通过逗号的个数来进行终止条件的判断。如果有三个逗号并且切割后的最后一段仍然符合ip地址的规范,那么就是一个合法的地址。
单层逻辑:
startIndex的起始是从i+2开始,因为如果前面的地址符合要求会拼接一个“,”
for (int i = startIndex; i < s.size(); i++) {
if (isValid(s, startIndex, i)) { // 判断 [startIndex,i] 这个区间的子串是否合法
s.insert(s.begin() + i + 1 , '.'); // 在i的后面插入一个逗点
pointNum++;
backtracking(s, i + 2, pointNum); // 插入逗点之后下一个子串的起始位置为i+2
pointNum--; // 回溯
s.erase(s.begin() + i + 1); // 回溯删掉逗点
} else break; // 不合法,直接结束本层循环
}
首先是判断区间的子串是否合法,子串切割的范围是startIndex,i
如果合法,在i的后面插入一个,来标识切割,逗号的个数+1(用来判断终止条件)
startIndex = i+2 : 从切割的位置后面进行新一轮的切割判断,直到所有的都满足条件或者不满足条件返回,进行回溯,从当前的前一步进行遍历性尝试。回溯逗号的拼接和逗号的个数。
分割类型的题目,难点在于对于分割线的理解,终止条件和分割线范围的写法是一个难点。
java代码:
class Solution { List<String> result = new ArrayList<>(); public List<String> restoreIpAddresses(String s) { if (s.length() > 12) return result; // 算是剪枝了 backTrack(s, 0, 0); return result; } // startIndex: 搜索的起始位置, pointNum:添加逗点的数量 private void backTrack(String s, int startIndex, int pointNum) { if (pointNum == 3) {// 逗点数量为3时,分隔结束 // 判断第四段⼦字符串是否合法,如果合法就放进result中 if (isValid(s,startIndex,s.length()-1)) { result.add(s); } return; } for (int i = startIndex; i < s.length(); i++) { if (isValid(s, startIndex, i)) { s = s.substring(0, i + 1) + "." + s.substring(i + 1); //在str的后⾯插⼊⼀个逗点 pointNum++; backTrack(s, i + 2, pointNum);// 插⼊逗点之后下⼀个⼦串的起始位置为i+2 pointNum--;// 回溯 s = s.substring(0, i + 1) + s.substring(i + 2);// 回溯删掉逗点 } else { break; } } } // 判断字符串s在左闭⼜闭区间[start, end]所组成的数字是否合法 private Boolean isValid(String s, int start, int end) { if (start > end) { return false; } if (s.charAt(start) == '0' && start != end) { // 0开头的数字不合法 return false; } int num = 0; for (int i = start; i <= end; i++) { if (s.charAt(i) > '9' || s.charAt(i) < '0') { // 遇到⾮数字字符不合法 return false; } num = num * 10 + (s.charAt(i) - '0'); if (num > 255) { // 如果⼤于255了不合法 return false; } } return true; } } //方法一:但使用stringBuilder,故优化时间、空间复杂度,因为向字符串插入字符时无需复制整个字符串,从而减少了操作的时间复杂度,也不用开新空间存subString,从而减少了空间复杂度。 class Solution { List<String> result = new ArrayList<>(); public List<String> restoreIpAddresses(String s) { StringBuilder sb = new StringBuilder(s); backTracking(sb, 0, 0); return result; } private void backTracking(StringBuilder s, int startIndex, int dotCount){ if(dotCount == 3){ if(isValid(s, startIndex, s.length() - 1)){ result.add(s.toString()); } return; } for(int i = startIndex; i < s.length(); i++){ if(isValid(s, startIndex, i)){ s.insert(i + 1, '.'); backTracking(s, i + 2, dotCount + 1); s.deleteCharAt(i + 1); }else{ break; } } } //[start, end] private boolean isValid(StringBuilder s, int start, int end){ if(start > end) return false; if(s.charAt(start) == '0' && start != end) return false; int num = 0; for(int i = start; i <= end; i++){ int digit = s.charAt(i) - '0'; num = num * 10 + digit; if(num > 255) return false; } return true; } } //方法二:比上面的方法时间复杂度低,更好地剪枝,优化时间复杂度 class Solution { List<String> result = new ArrayList<String>(); StringBuilder stringBuilder = new StringBuilder(); public List<String> restoreIpAddresses(String s) { restoreIpAddressesHandler(s, 0, 0); return result; } // number表示stringbuilder中ip段的数量 public void restoreIpAddressesHandler(String s, int start, int number) { // 如果start等于s的长度并且ip段的数量是4,则加入结果集,并返回 if (start == s.length() && number == 4) { result.add(stringBuilder.toString()); return; } // 如果start等于s的长度但是ip段的数量不为4,或者ip段的数量为4但是start小于s的长度,则直接返回 if (start == s.length() || number == 4) { return; } // 剪枝:ip段的长度最大是3,并且ip段处于[0,255] for (int i = start; i < s.length() && i - start < 3 && Integer.parseInt(s.substring(start, i + 1)) >= 0 && Integer.parseInt(s.substring(start, i + 1)) <= 255; i++) { // 如果ip段的长度大于1,并且第一位为0的话,continue if (i + 1 - start > 1 && s.charAt(start) - '0' == 0) { continue; } stringBuilder.append(s.substring(start, i + 1)); // 当stringBuilder里的网段数量小于3时,才会加点;如果等于3,说明已经有3段了,最后一段不需要再加点 if (number < 3) { stringBuilder.append("."); } number++; restoreIpAddressesHandler(s, i + 1, number); number--; // 删除当前stringBuilder最后一个网段,注意考虑点的数量的问题 stringBuilder.delete(start + number, i + number + 2); } } }