算法训练营第25天回溯（分割）

回溯算法（分割）

131.分割回文串

力扣题目链接(opens new window)

题目

给定一个字符串 s，将 s 分割成一些子串，使每个子串都是回文串。

返回 s 所有可能的分割方案。

示例: 输入: “aab” 输出: [ [“aa”,“b”], [“a”,“a”,“b”] ]

解答

在这里插入图片描述

每一个for都是一行

每个递归都是一个树枝

1.for

for (int i = index; i < s.length(); i++) {path.add(s.substring(index,i + 1));

表示每次的切割方案，对于深度相同的一层，切割的起始位置不变，截取长度不同，即第一次for截取a，第二层for截取aa，第三层for截取aab

2.递归

backtracking(s, i+1);

切割当前的之后，再切割剩余的字符串

3.回溯

path.removeLast();只要当前程序终止，表示切割完毕或者切割失败，就要回溯到上一层重新切割

4.终止条件

		if (!path.isEmpty() && !isPalindrome(path.getLast()))return;//如果新加入的并不是回文串，就终止，即错误切割的终止条件，当前的切割方案并不合适if (index >= s.length()){results.add(new ArrayList<>(path));return;}//深度达到最深的终止条件，即成功切割的终止条件

完整代码

class Solution {List<List<String>> results = new ArrayList<>();LinkedList<String> path = new LinkedList<>();public List<List<String>> partition(String s) {backtracking(s,0);return results;}void backtracking(String s,int index){if (index >= s.length()){results.add(new ArrayList<>(path));return;}//深度达到最深的终止条件，即成功切割的终止条件for (int i = index; i < s.length(); i++) {//横向切割，每个for都是一种切割方案，即横向遍历String subs = s.substring(index,i+1);if (isPalindrome(subs)){path.add(s.substring(index,i + 1));backtracking(s, i+1);//纵向遍历path.removeLast();}}}private boolean isPalindrome(String s){int startIndex = 0;int endIndex = s.length() - 1;while (startIndex <= endIndex){if (s.charAt(startIndex) != s.charAt(endIndex))return false;startIndex++;endIndex--;}return true;}
}

93.复原IP地址

力扣题目链接(opens new window)

题目

给定一个只包含数字的字符串，复原它并返回所有可能的 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 地址。

示例 1：

输入：s = “25525511135”
输出：[“255.255.11.135”,“255.255.111.35”]

示例 2：

输入：s = “0000”
输出：[“0.0.0.0”]

示例 3：

输入：s = “1111”
输出：[“1.1.1.1”]

示例 4：

输入：s = “010010”
输出：[“0.10.0.10”,“0.100.1.0”]

示例 5：

输入：s = “101023”
输出：[“1.0.10.23”,“1.0.102.3”,“10.1.0.23”,“10.10.2.3”,“101.0.2.3”]

提示：

0 <= s.length <= 3000
s 仅由数字组成

解答

在这里插入图片描述

主要是终止条件

如果ip已经>4，就没有继续的必要，该树枝结束if (ip.size() > 4) return;
如果加入的数字比225大，也可以结束if (!ip.isEmpty() && Integer.parseInt(ip.getLast()) > 255) return;
如果加入的字符串有超过两位并且第一位为0，也就结束if (!ip.isEmpty() && ip.getLast().length() > 1 && ip.getLast().charAt(0) == '0')
因为每次的startIndex都是i + 1，而i + 1恰巧是这一轮的startIndex，那么如果i + 1恰好为s.length()，也就表示刚好到达了末尾并且ip有四位，完美的结束if (ip.size() == 4 && startIndex == s.length())
for中的i < s.length() && i - startIndex < 3相当于剪枝，因为截取的长度最大也就只有三个

class Solution {List<String> results = new ArrayList<>();LinkedList<String> ip = new LinkedList<>();public List<String> restoreIpAddresses(String s) {if (s.length() > 3 && s.length() < 13)backtracking(s,0);return results;}void backtracking(String s,int startIndex){if (ip.size() > 4) return;if (!ip.isEmpty() && Integer.parseInt(ip.getLast()) > 255) return;if (!ip.isEmpty() && ip.getLast().length() > 1 && ip.getLast().charAt(0) == '0') return;if (ip.size() == 4 && startIndex == s.length()){StringBuilder result = new StringBuilder();for (int i = 0; i < ip.size() - 1; i++) {result.append(ip.get(i)).append(".");}result.append(ip.getLast());results.add(result.toString());return;}for (int i = startIndex; i < s.length() && i - startIndex < 3; i++) {String subs = s.substring(startIndex,i+1);ip.add(subs);backtracking(s,i+1);ip.removeLast();}}
}