LeetCode 93. 复原 IP 地址

比眉伴天荒 2022-11-04 13:29 195阅读 0赞

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl8zODE5OTc3MA_size_16_color_FFFFFF_t_70]  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl8zODE5OTc3MA_size_16_color_FFFFFF_t_70 1]  
[大佬][Link 1]

import java.util.ArrayDeque;
    import java.util.ArrayList;
    import java.util.Deque;
    import java.util.List;
    import java.util.Stack;
    
    public class Solution {
        
    
        public List<String> restoreIpAddresses(String s) {
        
            int len = s.length();
            List<String> res = new ArrayList<>();
            // 如果长度不够，不搜索
            if (len < 4 || len > 12) {
        
                return res;
            }
    
            Deque<String> path = new ArrayDeque<>(4);
            int splitTimes = 0;
            dfs(s, len, splitTimes, 0, path, res);
            return res;
        }
    
        /**
         * 判断 s 的子区间 [left, right] 是否能够成为一个 ip 段
         * 判断的同时顺便把类型转了
         *
         * @param s
         * @param left
         * @param right
         * @return
         */
        private int judgeIfIpSegment(String s, int left, int right) {
        
            int len = right - left + 1;
    
            // 大于 1 位的时候，不能以 0 开头
            if (len > 1 && s.charAt(left) == '0') {
        
                return -1;
            }
    
            // 转成 int 类型
            int res = 0;
            for (int i = left; i <= right; i++) {
        
                res = res * 10 + s.charAt(i) - '0';
            }
    
            if (res > 255) {
        
                return -1;
            }
            return res;
        }
    
        private void dfs(String s, int len, int split, int begin, Deque<String> path, List<String> res) {
        
            if (begin == len) {
        
                if (split == 4) {
        
                    res.add(String.join(".", path));
                }
                return;
            }
    
            // 看到剩下的不够了，就退出（剪枝），len - begin 表示剩余的还未分割的字符串的位数
            if (len - begin < (4 - split) || len - begin > 3 * (4 - split)) {
        
                return;
            }
    
            for (int i = 0; i < 3; i++) {
        
                if (begin + i >= len) {
        
                    break;
                }
    
                int ipSegment = judgeIfIpSegment(s, begin, begin + i);
                if (ipSegment != -1) {
        
                    // 在判断是 ip 段的情况下，才去做截取
                    path.addLast(ipSegment + "");
                    dfs(s, len, split + 1, begin + i + 1, path, res);
                    path.removeLast();
                }
            }
        }
    }

[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl8zODE5OTc3MA_size_16_color_FFFFFF_t_70]: /images/20221023/5a55dbf35daf48ca86de66ee25ab1510.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl8zODE5OTc3MA_size_16_color_FFFFFF_t_70 1]: /images/20221023/c872d0edc0fc49cea8005923f9a6caa4.png
[Link 1]: https://leetcode-cn.com/problems/restore-ip-addresses/solution/hui-su-suan-fa-hua-tu-fen-xi-jian-zhi-tiao-jian-by/