93. 复原 IP 地址

た入场券 2024-03-31 13:39 33阅读 0赞

### 93. 复原 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 地址。  
给定一个只包含数字的字符串 s ，用以表示一个 IP 地址，返回所有可能的有效 IP 地址，这些地址可以通过在 s 中插入 ‘.’ 来形成。你 不能 重新排序或删除 s 中的任何数字。你可以按 任何 顺序返回答案。

##### 示例 1： #####

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

##### 示例 2： #####

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

##### 示例 3： #####

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

##### 提示： #####

1 <= s.length <= 20  
s 仅由数字组成

#### 思路：（回溯） ####

**回溯算法事实上就是在一个树形问题上做深度优先遍历，因此 首先需要把问题转换为树形问题。**

1.  一开始，字符串的长度小于 4 或者大于 12 ，一定不能拼凑出合法的 ip 地址；
2.  由于 ip 段最多就 4 个段，因此这棵三叉树最多 4 层，这个条件作为递归终止条件之一；
3.  每一个结点可以选择截取的方法只有 3 种：截 1 位、截 2 位、截 3 位，因此每一个结点可以生长出的分支最多只有 3 条分支；
4.  根据截取出来的字符串判断是否是合理的 ip 段
5.  每一个结点表示了求解这个问题的不同阶段，需要的状态变量有：
    
     *  k：已经分割出多少个 ip 段；
     *  s：剩余字符串；
     *  temAddress：记录从根结点到叶子结点的一个路径（回溯算法常规变量，是一个栈）；
     *  addresses：记录结果集的变量，常规变量。

##### 代码：（Java） #####

import java.util.ArrayList;
    import java.util.List;
    
    public class restore_IP {
        
    
    	public static void main(String[] args) {
        
    		// TODO 自动生成的方法存根
    		String s = "101023";
    		System.out.println(restoreIpAddresses(s));
    	}
    	 public static List<String> restoreIpAddresses(String s) {
        
    		 List<String> addresses  = new ArrayList<>();
    		 if(s.length() < 4 || s.length() > 12) {
        
    			 return addresses;
    		 }
    		 doRestore(new StringBuilder(), addresses, s, 0);
    		 return addresses;
    	 }
    	private static void doRestore(StringBuilder temAddress, List<String> addresses, String s, int k) {
        
    		// TODO 自动生成的方法存根
    		if(k == 4 || s.length() == 0) {
        
    			if(k == 4 && s.length() == 0) {
        
    				addresses.add(temAddress.toString());
    			}
    			return;
    		}
    		for(int i = 0; i < s.length() && i <= 2; i++) {
        
    			if(i != 0 && s.charAt(0) == '0') {
        
    				break;
    			}
    			String part = s.substring(0, i + 1);
    			if(Integer.valueOf(part) <= 255) {
        
    				if(temAddress.length() != 0) {
        
    					part = "." + part;
    				}
    				temAddress.append(part);
    				doRestore(temAddress, addresses, s.substring(i + 1), k + 1);
    				temAddress.delete(temAddress.length() - part.length(), temAddress.length());
    			}
    		}
    		
    	}
    }

##### 输出： #####

![在这里插入图片描述][35c63842cfbb45c8b0587897fa5f673e.png]

##### 复杂度分析： #####

我们用 N=4 表示 IP 地址的段数。

*  时间复杂度： O ( 3 N × ∣ s ∣ ) O(3^N×∣s∣) O(3N×∣s∣)。由于 IP 地址的每一段的位数不会超过 3，因此在递归的每一层，我们最多只会深入到下一层的 3 种情况。由于 N=4，对应着递归的最大层数，所以递归本身的时间复杂度为  O ( 3 N ) O(3^N) O(3N)。如果我们复原出了一种满足题目要求的 IP 地址，那么需要 O(∣s∣) 的时间将其加入答案数组中，因此总时间复杂度为  O ( 3 N × ∣ s ∣ ) O(3^N×∣s∣) O(3N×∣s∣)。
 *  空间复杂度：O(N)，这里只计入除了用来存储答案以外的额外空间复杂度。递归使用的空间与递归的最大深度 N 成正比。并且在上面的代码中，我们只额外使用了长度为 N 的栈 存储已经搜索过的 IP 地址，因此空间复杂度为 O(N)。

##### 注：仅供学习参考 #####

题目来源：[力扣][Link 1].

[35c63842cfbb45c8b0587897fa5f673e.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/31/900c72e7f4104f978d678e331e1765f2.png
[Link 1]: https://leetcode.cn/problems/restore-ip-addresses/description/