Computing All Valid IP Addresses From Raw IP String

Question

I'm now solving leetcode problem 93. Restore IP Addresses.

Here's the url link: https://leetcode.com/problems/restore-ip-addresses/

The description looks like this: Given a string s containing only digits. Return all possible valid IP addresses that can be obtained from s. You can return them in any order.

A valid IP address consists of exactly four integers, each integer is between 0 and 255, separated by single points and cannot have leading zeros. For example, "0.1.2.201" and "192.168.1.1" are valid IP addresses and "0.011.255.245", "192.168.1.312" and "192.168@1.1" are invalid IP addresses.

However, as I was trying to solve my problem via backtracking, I couldn't figure out the reason that I'm always returning an empty ArrayList. I double checked my base case and my recursion and still couldn't find the bug. Any help would be greatly appreciated, thank you!

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

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.