算法-复原 IP 地址

墨蓝 2023-10-03 22:51 7阅读 0赞

#### 文章目录 ####

*  1. 有效 IP 问题
 *  2. 解法

## 1. 有效 IP 问题 ##

一个有效的 IP 地址由四个整数组成，每个整数位于 0 到 255 之间，且不能含有前导 0，整数之间用 `.` 分隔。给定一个只包含数字的字符串 s ，用以表示一个 IP 地址候选，返回所有可能的有效 IP 地址，[LeetCode 原题][LeetCode]

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

## 2. 解法 ##

> 回溯法，使用额外数组作为解空间，循环处理输入字符串的各个部分，确定一个有效 IP 整数段则将其加入解空间递归深入，直到处理至字符串末尾，最终确定一组 IP 整数段则递归返回

private List<String> res = new ArrayList<>();
       
        private Deque<String> sb = new ArrayDeque<>();
       
        public List<String> restoreIpAddresses(String s) {
        
            if (null == s || "".equals(s)) {
        
                return res;
            }
            backTracking(s, 0);
            return res;
        }
    
        public void backTracking(String s, int startIndex) {
        
            // 存储了 4 个段需要 return
            if (sb.size() == 4) {
        
                // 如果遍历的字符达到字符串末尾，可以认为找到了一个 ip
                if (startIndex == s.length()) {
        
                    res.add(String.join(".", sb));
                }
                return;
            }
    
            for (int i = startIndex; i < s.length(); i++) {
        
                if (!isValid(s, startIndex, i)) {
        
                    // 不合法的话直接结束本层循环
                    break;
                }
                sb.addLast(s.substring(startIndex, i + 1));
                backTracking(s, i + 1);
                sb.removeLast();
            }
        }
    
        public boolean isValid(String s, int start, int end) {
        
            if (start > end) {
        
                return false;
            }
            if ('0' == s.charAt(start) && start != end) {
        
                return false;
            }
    
            int count = 0;
            for (int i = start; i <= end; i++) {
        
                char c = s.charAt(i);
                if (c > '9' || c < '0') {
        
                    return false;
                }
                count = count * 10 + (c - '0');
                if (count > 255) {
        
                    return false;
                }
            }
            return true;
        }

[LeetCode]: https://leetcode.cn/problems/restore-ip-addresses/