分割回文串 复原IP地址（Java）
分割回文串
关键点：
- 递归如何终止：当startIndex == s.length() （注意没有-1是因为这一步操作不会继续进行）
- 在递归循环中如何截取子串：关键在于在每个栈都创建属于自己的StringBuffer（！！！很关键，这样就不会在每次换栈的时候手动删除sb），在自己的基础上append即可。
- 如何判断回文：类似数组中的左右指针
- !!!只有在字符串判断为回文串时才进行递归
/**end其实是不变，虽然每层循环个数不一样，但是每层循环的其实位置也不一样 */
class Solution {List<List<String>> res = new ArrayList<>();List<String> sub = new ArrayList<>();public List<List<String>> partition(String s) {StringBuffer sb = new StringBuffer();fucPartition(s, 0, sb);return res;}public void fucPartition(String s, int startIndex, StringBuffer sb){ //每个里边有自己的sb// 递归终止条件if(startIndex == s.length() ){res.add(new ArrayList<>(sub));return;}for(int i = startIndex; i < s.length(); i++){//截取字串sb.append(s.charAt(i));// 判断是否位回文串if(isTrue(sb)){sub.add(sb.toString()); // 这个别忘了fucPartition(s, i + 1, new StringBuffer()); //创建新的sbsub.remove(sub.size() - 1);//sub.remove(sub.size() - 1); }else{ //如果不是说明分割方式错误continue; // 不再往下进行}}}//判断字符串是不是回文public boolean isTrue(StringBuffer sb){int left = 0;int right = sb.length() - 1;while(left < right){if(sb.charAt(left) == sb.charAt(right)){left++;right--;}else{return false;}}return true;}
}
写博客的目的是每日督促并记录刷题，也欢迎大家批评指正~（day26）(呜呜隔了好多天了，后边要更加油！！)
复原IP地址
我在这里用容器装路径。
思路类似于分割回文串，主要两种不同：
- 递归终止条件：够四个数就终止
- 判断是否有效性：这里的代码思路是，先保证截取的字符串不能超过3位数，并且如果首位为0说明该字符串只能有一位，如果满足以上条件再将字符串转成int，看是否在0-255范围内。
class Solution {List<String> res = new ArrayList<>();List<Integer> sub = new ArrayList<>();public List<String> restoreIpAddresses(String s) {// 层数的话必须要是四个，并且回溯的本质是枚举if(s.length() < 4 || s.length() > 12){return res; //整体剪枝}fucIp(s, 0, new StringBuffer());return res;}public void fucIp(String s, int startIndex, StringBuffer sb){ //切割字符串，用sb记录自己的情况if(sub.size() == 4){// 正好处理完if(startIndex == s.length()){StringBuffer sbu = new StringBuffer();for(int i : sub){sbu.append(i).append(".");}sbu.deleteCharAt(sbu.length() - 1);res.add(sbu.toString());}return;}for(int i = startIndex; i < s.length(); i++){sb.append(s.charAt(i));if(isTrue(sb.toString())){ // 如果有效就加入进去sub.add(Integer.parseInt(sb.toString()));fucIp(s, i + 1, new StringBuffer());sub.remove(sub.size() - 1);}}}//判断整数是不是有效的public boolean isTrue(String s){//这儿的条件之前考虑不全if(s.charAt(0) == '0' && s.length() > 1){return false;}if(s.length() > 3){return false;}int i = Integer.parseInt(s); // 字符串强转为intif(i < 0 || i > 255){return false;}return true;}
}