时间戳

首页 > 解决方案 > 从原始 IP 字符串计算所有有效 IP 地址

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

问题描述

我现在正在解决 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

        }
    }

标签： javabacktracking

解决方案

You have written a pretty advanced code. It's working for all the cases where IP address segment is lower than 225, but the first test case has 255s in there.

The fix is trivial, just replace "val > 225" to "val > 255".

It should be like this:

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

P.S. I would do this differently, I would add dots into every possible place and validate every received combination.

推荐阅读