题

目链接

LeetCode

题目描述

给定一个只包含数字的字符串，用以表示一个 IP 地址，返回所有可能从 s 获得的 有效 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 仅由数字组成
解题思路
方法一：回溯法
回溯算法事实上就是在一个树形问题上做深度优先遍历，因此首先需要把问题转换为树形问题。这里请大家一定要拿起纸和笔，模拟一下如何通过指定的字符串 s 生成 IP 地址的过程，把树形图画出来（这一点很重要）。

下面这张图我没有画完（如果画完，枝叶太多），请读者尽量不看我画的这张图，自己动手尝试一下这个问题的树形图应该怎么画。

在画树形图的过程中，你一定会发现有些枝叶是没有必要的，把没有必要的枝叶剪去的操作就是剪枝，在代码中一般通过 break 或者 contine 和 return （表示递归终止）实现。
93. 复原 IP 地址** - 图1
分析剪枝条件（下面只写出一些我想到的要点，有些点能想到，但是编码很复杂，我就没有写了）：

一开始，字符串的长度小于 4 或者大于 12 ，一定不能拼凑出合法的 ip 地址（这一点可以一般化到中间结点的判断中，以产生剪枝行为）；
每一个结点可以选择截取的方法只有 3 种：截 1 位、截 2 位、截 3 位，因此每一个结点可以生长出的分支最多只有 3 条分支；

根据截取出来的字符串判断是否是合理的 ip 段，这里写法比较多，可以先截取，再转换成 int ，再判断。我采用的做法是先转成 int，是合法的 ip 段数值以后，再截取。

由于 ip 段最多就 4 个段，因此这棵三叉树最多 4 层，这个条件作为递归终止条件之一；

每一个结点表示了求解这个问题的不同阶段，需要的状态变量有：

splitTimes：已经分割出多少个 ip 段；
begin：截取 ip 段的起始位置；
path：记录从根结点到叶子结点的一个路径（回溯算法常规变量，是一个栈）；

res：记录结果集的变量，常规变量。

class Solution {
public:
vector<string> restoreIpAddresses(string s) {
   len = s.length();
   if(len<4||len>12){
       return {};
   }
   dfs(s,0,4);
   return res;
}
private:
int len = 0;
vector<string> path;
vector<string> res;
void dfs(string& s, int begin,int residue){
   if(begin==len){
       if(residue==0){
           string tmp;
           for(int i=0;i<3;i++){
               tmp = tmp + path[i]+".";
           }
           tmp += path[3];
           res.push_back(tmp);
       }
       return;
   }
   for(int i=begin;i<begin+3;i++){
       if(i>=len){
           break;
       }
       if(residue*3<len-i){
           continue;
       }
       if(judgeIpSegment(s,begin,i)){
           path.push_back(s.substr(begin,i-begin+1));
           dfs(s,i+1,residue-1);
           path.pop_back();
       }
   }
}
bool judgeIpSegment(string& s,int begin,int end){
   int len = end-begin+1;
   if(len>1&&s[begin]=='0')
       return false;
   int res = 0;
   while(begin<=end){
       res = res*10 + s[begin]-'0';
       begin++;
   }
   return res>=0&&res<=255;
}
};

```java class Solution { public List restoreIpAddresses(String s) { List res = new ArrayList(); if(s.length()<4||s.length()>12){

   return res;

} backtrack(res,new ArrayList(),0,4,s); return res; } private void backtrack(List res, List path, int begin, int residue, String s){ if(begin == s.length()){

   if(residue == 0){
       StringBuilder tmp = new StringBuilder();
       for(int i=0;i<3;i++){
           tmp.append(path.get(i));
           tmp.append('.');
       }
       tmp.append(path.get(3));
       res.add(tmp.toString());
   }

}else{

   for(int i=begin;i<begin+3;++i){
       if(i>=s.length()){
           break;
       }
       if(residue*3 < s.length()-i){
           continue;
       }
       if(judgeIpSement(s,begin,i)){
           path.add(s.substring(begin,i+1));
           backtrack(res,path,i+1,residue-1,s);
           path.remove(4-residue);
       }
   }

} } private boolean judgeIpSement(String s,int begin,int end){ int len = end - begin + 1; if(len>1&&s.charAt(begin) == ‘0’){

   return false;

} int res = 0; for(int i=begin;i<=end;i++){

   res = res*10 + (s.charAt(i)-'0');

} return res>=0&&res<=255; }

} ```

时间复杂度 :因为这个问题限制在有效 IP 段内，因此需要截取和检查的次数有上限，分析清楚这个复杂度在我的能力范围之外（欢迎大家指导）。很多回溯问题的复杂度分析都比较 “复杂”，所以我选择暂时搁浅。
空间复杂度 O(h)

93. 复原 IP 地址**

题

目链接

题目描述

解题思路

方法一：回溯法