参与本项目,贡献其他语言版本的代码,拥抱开源,让更多学习算法的小伙伴们收益!
给定一个只包含数字的字符串,复原它并返回所有可能的 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 仅由数字组成
做这道题目之前,最好先把131.分割回文串这个做了。
这道题目相信大家刚看的时候,应该会一脸茫然。
其实只要意识到这是切割问题,切割问题就可以使用回溯搜索法把所有可能性搜出来,和刚做过的131.分割回文串就十分类似了。
切割问题可以抽象为树型结构,如图:
- 递归参数
在131.分割回文串中我们就提到切割问题类似组合问题。
startIndex一定是需要的,因为不能重复分割,记录下一层递归分割的起始位置。
本题我们还需要一个变量pointNum,记录添加逗点的数量。
所以代码如下:
vector<string> result;// 记录结果
// startIndex: 搜索的起始位置,pointNum:添加逗点的数量
void backtracking(string& s, int startIndex, int pointNum) {
- 递归终止条件
终止条件和131.分割回文串情况就不同了,本题明确要求只会分成4段,所以不能用切割线切到最后作为终止条件,而是分割的段数作为终止条件。
pointNum表示逗点数量,pointNum为3说明字符串分成了4段了。
然后验证一下第四段是否合法,如果合法就加入到结果集里
代码如下:
if (pointNum == 3) { // 逗点数量为3时,分隔结束
// 判断第四段子字符串是否合法,如果合法就放进result中
if (isValid(s, startIndex, s.size() - 1)) {
result.push_back(s);
}
return;
}
- 单层搜索的逻辑
在131.分割回文串中已经讲过在循环遍历中如何截取子串。
在for (int i = startIndex; i < s.size(); i++)
循环中 [startIndex, i] 这个区间就是截取的子串,需要判断这个子串是否合法。
如果合法就在字符串后面加上符号.
表示已经分割。
如果不合法就结束本层循环,如图中剪掉的分支:
然后就是递归和回溯的过程:
递归调用时,下一层递归的startIndex要从i+2开始(因为需要在字符串中加入了分隔符.
),同时记录分割符的数量pointNum 要 +1。
回溯的时候,就将刚刚加入的分隔符.
删掉就可以了,pointNum也要-1。
代码如下:
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; // 不合法,直接结束本层循环
}
最后就是在写一个判断段位是否是有效段位了。
主要考虑到如下三点:
- 段位以0为开头的数字不合法
- 段位里有非正整数字符不合法
- 段位如果大于255了不合法
代码如下:
// 判断字符串s在左闭又闭区间[start, end]所组成的数字是否合法
bool isValid(const string& s, int start, int end) {
if (start > end) {
return false;
}
if (s[start] == '0' && start != end) { // 0开头的数字不合法
return false;
}
int num = 0;
for (int i = start; i <= end; i++) {
if (s[i] > '9' || s[i] < '0') { // 遇到非数字字符不合法
return false;
}
num = num * 10 + (s[i] - '0');
if (num > 255) { // 如果大于255了不合法
return false;
}
}
return true;
}
根据关于回溯算法,你该了解这些!给出的回溯算法模板:
void backtracking(参数) {
if (终止条件) {
存放结果;
return;
}
for (选择:本层集合中元素(树中节点孩子的数量就是集合的大小)) {
处理节点;
backtracking(路径,选择列表); // 递归
回溯,撤销处理结果
}
}
可以写出如下回溯算法C++代码:
class Solution {
private:
vector<string> result;// 记录结果
// startIndex: 搜索的起始位置,pointNum:添加逗点的数量
void backtracking(string& s, int startIndex, int pointNum) {
if (pointNum == 3) { // 逗点数量为3时,分隔结束
// 判断第四段子字符串是否合法,如果合法就放进result中
if (isValid(s, startIndex, s.size() - 1)) {
result.push_back(s);
}
return;
}
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; // 不合法,直接结束本层循环
}
}
// 判断字符串s在左闭又闭区间[start, end]所组成的数字是否合法
bool isValid(const string& s, int start, int end) {
if (start > end) {
return false;
}
if (s[start] == '0' && start != end) { // 0开头的数字不合法
return false;
}
int num = 0;
for (int i = start; i <= end; i++) {
if (s[i] > '9' || s[i] < '0') { // 遇到非数字字符不合法
return false;
}
num = num * 10 + (s[i] - '0');
if (num > 255) { // 如果大于255了不合法
return false;
}
}
return true;
}
public:
vector<string> restoreIpAddresses(string s) {
result.clear();
if (s.size() > 12) return result; // 算是剪枝了
backtracking(s, 0, 0);
return result;
}
};
在131.分割回文串中我列举的分割字符串的难点,本题都覆盖了。
而且本题还需要操作字符串添加逗号作为分隔符,并验证区间的合法性。
可以说是131.分割回文串的加强版。
在本文的树形结构图中,我已经把详细的分析思路都画了出来,相信大家看了之后一定会思路清晰不少!
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;
}
}
//方法二:比上面的方法时间复杂度低,更好地剪枝,优化时间复杂度
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);
}
}
}
python2:
class Solution(object):
def restoreIpAddresses(self, s):
"""
:type s: str
:rtype: List[str]
"""
ans = []
path = []
def backtrack(path, startIndex):
if len(s) > 12: return []
if len(path) == 4:
if startIndex == len(s):
ans.append(".".join(path[:]))
return
for i in range(startIndex+1, min(startIndex+4, len(s)+1)): # 剪枝
string = s[startIndex:i]
if not 0 <= int(string) <= 255:
continue
if not string == "0" and not string.lstrip('0') == string:
continue
path.append(string)
backtrack(path, i)
path.pop()
backtrack([], 0)
return ans
python3:
class Solution:
def __init__(self):
self.result = []
def restoreIpAddresses(self, s: str) -> List[str]:
'''
本质切割问题使用回溯搜索法,本题只能切割三次,所以纵向递归总共四层
因为不能重复分割,所以需要start_index来记录下一层递归分割的起始位置
添加变量point_num来记录逗号的数量[0,3]
'''
self.result.clear()
if len(s) > 12: return []
self.backtracking(s, 0, 0)
return self.result
def backtracking(self, s: str, start_index: int, point_num: int) -> None:
# Base Case
if point_num == 3:
if self.is_valid(s, start_index, len(s)-1):
self.result.append(s[:])
return
# 单层递归逻辑
for i in range(start_index, len(s)):
# [start_index, i]就是被截取的子串
if self.is_valid(s, start_index, i):
s = s[:i+1] + '.' + s[i+1:]
self.backtracking(s, i+2, point_num+1) # 在填入.后,下一子串起始后移2位
s = s[:i+1] + s[i+2:] # 回溯
else:
# 若当前被截取的子串大于255或者大于三位数,直接结束本层循环
break
def is_valid(self, s: str, start: int, end: int) -> bool:
if start > end: return False
# 若数字是0开头,不合法
if s[start] == '0' and start != end:
return False
if not 0 <= int(s[start:end+1]) <= 255:
return False
return True
/**
* @param {string} s
* @return {string[]}
*/
var restoreIpAddresses = function(s) {
const res = [], path = [];
backtracking(0, 0)
return res;
function backtracking(i) {
const len = path.length;
if(len > 4) return;
if(len === 4 && i === s.length) {
res.push(path.join("."));
return;
}
for(let j = i; j < s.length; j++) {
const str = s.substr(i, j - i + 1);
if(str.length > 3 || +str > 255) break;
if(str.length > 1 && str[0] === "0") break;
path.push(str);
backtracking(j + 1);
path.pop()
}
}
};
回溯(对于前导 0的IP(特别注意s[startIndex]=='0'的判断,不应该写成s[startIndex]==0,因为s截取出来不是数字))
func restoreIpAddresses(s string) []string {
var res,path []string
backTracking(s,path,0,&res)
return res
}
func backTracking(s string,path []string,startIndex int,res *[]string){
//终止条件
if startIndex==len(s)&&len(path)==4{
tmpIpString:=path[0]+"."+path[1]+"."+path[2]+"."+path[3]
*res=append(*res,tmpIpString)
}
for i:=startIndex;i<len(s);i++{
//处理
path:=append(path,s[startIndex:i+1])
if i-startIndex+1<=3&&len(path)<=4&&isNormalIp(s,startIndex,i){
//递归
backTracking(s,path,i+1,res)
}else {//如果首尾超过了3个,或路径多余4个,或前导为0,或大于255,直接回退
return
}
//回溯
path=path[:len(path)-1]
}
}
func isNormalIp(s string,startIndex,end int)bool{
checkInt,_:=strconv.Atoi(s[startIndex:end+1])
if end-startIndex+1>1&&s[startIndex]=='0'{//对于前导 0的IP(特别注意s[startIndex]=='0'的判断,不应该写成s[startIndex]==0,因为s截取出来不是数字)
return false
}
if checkInt>255{
return false
}
return true
}
//记录结果
char** result;
int resultTop;
//记录应该加入'.'的位置
int segments[3];
int isValid(char* s, int start, int end) {
if(start > end)
return 0;
if (s[start] == '0' && start != end) { // 0开头的数字不合法
return false;
}
int num = 0;
for (int i = start; i <= end; i++) {
if (s[i] > '9' || s[i] < '0') { // 遇到非数字字符不合法
return false;
}
num = num * 10 + (s[i] - '0');
if (num > 255) { // 如果大于255了不合法
return false;
}
}
return true;
}
//startIndex为起始搜索位置,pointNum为'.'对象
void backTracking(char* s, int startIndex, int pointNum) {
//若'.'数量为3,分隔结束
if(pointNum == 3) {
//若最后一段字符串符合要求,将当前的字符串放入result种
if(isValid(s, startIndex, strlen(s) - 1)) {
char* tempString = (char*)malloc(sizeof(char) * strlen(s) + 4);
int j;
//记录添加字符时tempString的下标
int count = 0;
//记录添加字符时'.'的使用数量
int count1 = 0;
for(j = 0; j < strlen(s); j++) {
tempString[count++] = s[j];
//若'.'的使用数量小于3且当前下标等于'.'下标,添加'.'到数组
if(count1 < 3 && j == segments[count1]) {
tempString[count++] = '.';
count1++;
}
}
tempString[count] = 0;
//扩容result数组
result = (char**)realloc(result, sizeof(char*) * (resultTop + 1));
result[resultTop++] = tempString;
}
return ;
}
int i;
for(i = startIndex; i < strlen(s); i++) {
if(isValid(s, startIndex, i)) {
//记录应该添加'.'的位置
segments[pointNum] = i;
backTracking(s, i + 1, pointNum + 1);
}
else {
break;
}
}
}
char ** restoreIpAddresses(char * s, int* returnSize){
result = (char**)malloc(0);
resultTop = 0;
backTracking(s, 0, 0);
*returnSize = resultTop;
return result;
}
// 判断区间段是否合法
func isValid(s: [Character], start: Int, end: Int) -> Bool {
guard start <= end, start >= 0, end < s.count else { return false } // 索引不合法
if start != end, s[start] == "0" { return false } // 以0开头的多位数字不合法
var num = 0
for i in start ... end {
let c = s[i]
guard c >= "0", c <= "9" else { return false } // 非数字不合法
let value = c.asciiValue! - ("0" as Character).asciiValue!
num = num * 10 + Int(value)
guard num <= 255 else { return false } // 大于255不合法
}
return true
}
func restoreIpAddresses(_ s: String) -> [String] {
var s = Array(s) // 转换成字符数组以便于比较
var result = [String]() // 结果
func backtracking(startIndex: Int, pointCount: Int) {
guard startIndex < s.count else { return } // 索引不合法
// 结束条件
if pointCount == 3 {
// 最后一段也合法,则收集结果
if isValid(s: s, start: startIndex, end: s.count - 1) {
result.append(String(s))
}
return
}
for i in startIndex ..< s.count {
// 判断[starIndex, i]子串是否合法,合法则插入“.”,否则结束本层循环
if isValid(s: s, start: startIndex, end: i) {
s.insert(".", at: i + 1) // 子串后面插入“.”
backtracking(startIndex: i + 2, pointCount: pointCount + 1) // 注意这里时跳2位,且通过pointCount + 1局部变量隐藏了pointCount的回溯
s.remove(at: i + 1) // 回溯
} else {
break
}
}
}
backtracking(startIndex: 0, pointCount: 0)
return result
}