从原始 IP 字符串计算所有有效 IP 地址

Question

我现在正在解决 leetcode 问题 93。恢复 IP 地址。

这是网址链接：https : //leetcode.com/problems/restore-ip-addresses/

描述如下： 给定一个只包含数字的字符串 s。返回可以从 s 获取的所有可能的有效 IP 地址。您可以按任何顺序退回它们。

一个有效的 IP 地址正好由四个整数组成，每个整数都在 0 到 255 之间，用单点分隔，不能有前导零。例如，“0.1.2.201”和“192.168.1.1”是有效IP地址，“0.011.255.245”、“192.168.1.312”和“192.168@1.1”是无效IP地址。

然而，当我试图通过回溯解决我的问题时，我无法弄清楚我总是返回一个空的 ArrayList 的原因。我仔细检查了我的基本情况和我的递归，但仍然找不到错误。任何帮助将不胜感激，谢谢！

public List<String> restoreIpAddresses(String s) {
        List<String> res = new ArrayList<>();
        if(s.length() == 0){
            return res;
        }
        int[] path = new int[4];
        snapshotIP(res,s,0,path,0);
        return res;
    }
    
    public void snapshotIP(List<String> res, String s, int index, int[] path, int segment){
        if(segment == 4 && index == s.length()){
            res.add(path[0]+"."+path[1]+"."+path[2]+"."+path[3]);
            return;
        }
        else if(segment == 4 || index == s.length()){
            return;
        }
        for(int len = 1; len <= 3 && index + len <= s.length(); len++){
            String snap = s.substring(index,index+len);
            int val = Integer.parseInt(snap);
            if(val > 225 || len >= 2 && s.charAt(index) == '0'){
                break;
            }
            path[segment] = val;
            snapshotIP(res,s,index+len,path,segment+1);
            path[segment] = -1; //undo the choice

        }
    }

Answer 1

您已经编写了非常高级的代码。它适用于所有 IP 地址段低于 225 的情况，但第一个测试用例在那里有 255s。

修复很简单，只需将“val > 225”替换为“val > 2 5 5”。

应该是这样的：

if(val > 255 || len >= 2 && s.charAt(index) == '0')

PS我会以不同的方式做这件事，我会在每个可能的地方添加点并验证每个收到的组合。