LeetCode_回溯_中等_93.复原 IP 地址

谁践踏了优雅 2023-10-09 20:31 30阅读 0赞

#### 目录 ####

*  1.题目
 *  2.思路
 *  3.代码实现（Java）

## 1.题目 ##

有效 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 仅由数字组成

来源：力扣（LeetCode）  
链接：https://leetcode.cn/problems/restore-ip-addresses

## 2.思路 ##

（1）回溯  
思路参考[本题官方题解][Link 1]。

相关题目：  
[LeetCode\_字符串\_中等\_468.验证 IP 地址][LeetCode_468._ IP]

## 3.代码实现（Java） ##

//思路1————回溯
    class Solution {
        
    
        static final int SEG_COUNT = 4;
        List<String> res = new ArrayList<>();
        int[] segments = new int[SEG_COUNT];
    
        public List<String> restoreIpAddresses(String s) {
        
            backtrack(s, 0, 0);
            return res;
        }
    
        public void backtrack(String s, int segId, int segStart) {
        
            //如果找到了 4 段 IP 地址并且遍历完了字符串，那么就是一种答案
            if (segId == SEG_COUNT) {
        
                if (segStart == s.length()) {
        
                    StringBuilder builder = new StringBuilder();
                    for (int i = 0; i < SEG_COUNT; i++) {
        
                        builder.append(segments[i]);
                        if (i != SEG_COUNT - 1) {
        
                            builder.append('.');
                        }
                    }
                    res.add(builder.toString());
                }
                return;
            }
            //如果还没有找到 4 段 IP 地址就已经遍历完了字符串，那么提前回溯
            if (segStart == s.length()) {
        
                return;
            }
            //由于不能有前导零，如果当前数字为 0，那么这一段 IP 地址只能为 0
            if (s.charAt(segStart) == '0') {
        
                segments[segId] = 0;
                backtrack(s, segId + 1, segStart + 1);
            }
            //一般情况，枚举每一种可能性并递归
            int addr = 0;
            for (int segEnd = segStart; segEnd < s.length(); segEnd++) {
        
                addr = addr * 10 + (s.charAt(segEnd) - '0');
                if (addr > 0 && addr <= 255) {
        
                    segments[segId] = addr;
                    backtrack(s, segId + 1, segEnd + 1);
                } else {
        
                    break;
                }
            }
        }
    }

[Link 1]: https://leetcode.cn/problems/restore-ip-addresses/solution/fu-yuan-ipdi-zhi-by-leetcode-solution/
[LeetCode_468._ IP]: https://blog.csdn.net/weixin_43004044/article/details/132339991