切割问题概述

131. 分割回文串

  • 切割问题可以抽象为组合问题
  • 如何模拟那些切割线
  • 切割问题中递归如何终止
  • 在递归循环中如何截取子串
  • 如何判断回文

其实切割问题类似组合问题。例如对于字符串abcdef：

  • 组合问题：选取一个a之后，在bcdef中再去选取第二个，选取b之后在cdef中在选组第三个…..。
  • 切割问题：切割一个a之后，在bcdef中再去切割第二段，切割b之后在cdef中在切割第三段…..。

所以切割问题，也可以抽象为一棵树形结构，如图：
image.png

  1. class Solution {
  2.     List<List<String>> res = new ArrayList<>();
  3.     List<String> path = new ArrayList<>();
  4.     public List<List<String>> partition(String s) {
  5.         backtrack(s, 0);
  6.         return res;
  7.     }
  9.     public void backtrack(String s, int startIndex){
  10.         if (startIndex == s.length()) {
  11.             res.add(new ArrayList<>(path));//这里不需要判断是因为最后一个切割一定是单个字符，也就是一定是回文的
  12.             return;
  13.         }
  14.         for (int i = startIndex; i < s.length(); ++i) {
  15.             if (isPalindrome(s, startIndex, i)) {
  16.                 String substring = s.substring(startIndex, i + 1);
  17.                 path.add(substring);
  18.                 backtrack(s, i + 1); //这里是i + 1
  19.                 path.remove(path.size() - 1);
  20.             }else{
  21.                 break;
  22.             }
  23.         }
  24.     }
  26.     public boolean isPalindrome(String s, int start, int end){
  27.         for (int i = start, j = end; i < j; ++i, --j) {
  28.             if (s.charAt(i) != s.charAt(j)) {
  29.                 return false;
  30.             }
  31.         }
  32.         return true;
  33.     }
  34. }

93. 复原 IP 地址

  • 判断某段是ip地址这个函数中，最好不要用Integer.parseInt()，会爆int，按位计算只要大于255就不合法
  • 往字符串中插入新字符可以使用两个substring操作，同理删除也是一样。如果使用StringBuilder，会有insert和deleteCharAt函数，但是具体的位置不清楚。
  • 当分割点为3的时候，原字符串被分为了四份，因为前三份再添加的时候判断过了，只需要判断第四段是否为合法的ip即可

  • 下一层递归的时候，startIndex的位置应该是i+2，因为加了一个. ```java class Solution { List res = new ArrayList<>(); public List restoreIpAddresses(String s) {

    1.   if (s.length() > 12) { //剪枝
    2.       return res;
    3.   }
    4.   backtrack(s, 0, 0);
    5.   return res;

    }

    public void backtrack(String s, int startIndex, int pointsNum){

      if (pointsNum == 3) { //分隔符为三个的时候分割结束
      //判断第四段是否合法，合法则将结果放入
      if (isIP(s, startIndex, s.length() - 1)) {
          res.add(s);
      }
      return ;
  }
  for (int i = startIndex; i < s.length(); ++i) {
      if (isIP(s, startIndex, i)) {
          s = s.substring(0, i + 1) + "." + s.substring(i + 1);
          pointsNum++;
          backtrack(s, i + 2, pointsNum); //注意这里是+2
          pointsNum--;
          s = s.substring(0, i + 1) + s.substring(i + 2);
      } else {
          break;
      }
  }

    }

    public boolean isIP(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;
      }
  }

    // if (Integer.parseInt(s.substring(start, end + 1)) > 255) { // return false; // }

      return true;

    }

} ```