Computing All Valid IP Addresses From Raw IP String

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

        }
    }

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:
<!-- begin snippet: js hide: false console: true babel: false -->

<!-- language: lang-java -->

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

<!-- end snippet -->

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

Your code looks pretty good, not bad at all, not sure where your bug is though.

Here is an alternative solution, not so pretty though, it would pass just fine:

public final class Solution {
public static final List<String> restoreIpAddresses(
final String ip
) {
List<String> res = new ArrayList<>();
int length = ip.length();
for (int i = 1; i < 4 && i < length - 2; i++)
for (int j = i + 1; j < i + 4 && j < length - 1; j++)
for (int k = j + 1; k < j + 4 && k < length; k++) {
final String part1 = ip.substring(0, i);
final String part2 = ip.substring(i, j);
final String part3 = ip.substring(j, k);
final String part4 = ip.substring(k, length);
if (isValid(part1) && isValid(part2) && isValid(part3) && isValid(part4)) {
res.add(part1 + "." + part2 + "." + part3 + "." + part4);
}
}
return res;
}
private static final boolean isValid(
final String s
) {
if (s.length() > 3 || s.length() == 0 || (s.charAt(0) == '0' && s.length() > 1) || Integer.parseInt(s) > 255) {
return false;
}
return true;
}
}

Something a bit suspicious in your code is that the backtracking helper function is void, maybe you've to define a variable to make it work, still unsure.

Similarly in C++, if you'd be interested:

// The following block might slightly improve the execution time;
// Can be removed;
static const auto __optimize__ = []() {
std::ios::sync_with_stdio(false);
std::cin.tie(NULL);
std::cout.tie(NULL);
return 0;
}();
// Most of headers are already included;
// Can be removed;
#include <cstdint>
#include <vector>
#include <string>
#define LIMIT 256
using ValueType = std::uint_fast16_t;
static const struct Solution {
static const std::vector<std::string> restoreIpAddresses(
const std::string s
) {
const ValueType len = std::size(s);
std::vector<std::string> ips;
std::string ip;
ValueType a, b, c, d;
ValueType A, B, C, D;
for (a = 1; a < 4; ++a) {
for (b = 1; b < 4; ++b) {
for (c = 1; c < 4; ++c) {
for (d = 1; d < 4; ++d) {
if (a + b + c + d == len) {
A = std::stoi(s.substr(0, a));
B = std::stoi(s.substr(a, b));
C = std::stoi(s.substr(a + b, c));
D = std::stoi(s.substr(a + b + c, d));
if (A < LIMIT && B < LIMIT && C < LIMIT && D < LIMIT) {
ip = std::to_string(A) + "." +
std::to_string(B) + "." +
std::to_string(C) + "." +
std::to_string(D);
if (std::size(ip) == len + 3) {
ips.emplace_back(ip);
}
}
}
}
}
}
}
return ips;
}
};

Here is LeetCode's backtracking depth first search algorithm that is similar to yours, that might help you figure it out.

class Solution {
int n;
String s;
LinkedList<String> segments = new LinkedList<String>();
ArrayList<String> output = new ArrayList<String>();
public boolean valid(String segment) {
/*
Check if the current segment is valid :
1. less or equal to 255      
2. the first character could be '0' 
only if the segment is equal to '0'
*/
int m = segment.length();
if (m > 3)
return false;
return (segment.charAt(0) != '0') ? (Integer.valueOf(segment) <= 255) : (m == 1);
}
public void update_output(int curr_pos) {
/*
Append the current list of segments 
to the list of solutions
*/
String segment = s.substring(curr_pos + 1, n);
if (valid(segment)) {
segments.add(segment);
output.add(String.join(".", segments));
segments.removeLast();
}
}
public void backtrack(int prev_pos, int dots) {
/*
prev_pos : the position of the previously placed dot
dots : number of dots to place
*/
// The current dot curr_pos could be placed 
// in a range from prev_pos + 1 to prev_pos + 4.
// The dot couldn't be placed 
// after the last character in the string.
int max_pos = Math.min(n - 1, prev_pos + 4);
for (int curr_pos = prev_pos + 1; curr_pos < max_pos; curr_pos++) {
String segment = s.substring(prev_pos + 1, curr_pos + 1);
if (valid(segment)) {
segments.add(segment);  // place dot
if (dots - 1 == 0)      // if all 3 dots are placed
update_output(curr_pos);  // add the solution to output
else
backtrack(curr_pos, dots - 1);  // continue to place dots
segments.removeLast();  // remove the last placed dot 
}
}
}
public List<String> restoreIpAddresses(String s) {
n = s.length();
this.s = s;
backtrack(-1, 3);
return output;
}
}

References

• For additional details, please see the Discussion Board where you can find plenty of well-explained accepted solutions with a variety of languages including low-complexity algorithms and asymptotic runtime/memory analysis^{1, 2}.

internal static IEnumerable<string> FetchPossibleIPs(string input, int currentSection = 1)
{
List<string> possibleIPs = new List<string>();
if (input.Length > 0)
{
// If section is 4 then no need 
// to break further and simply verify.
if (currentSection == 4)
{
if (int.Parse(input) <= 255 && input[0].ToString() != "0")
{
possibleIPs.Add(input);
}
}
// Else if section is < 4 then break the string 
// with substring of length of 1,2 or 3 to 
// figure out possible combinations.
else
{
for (int i = 1; i <= 3; ++i)
{
var section = input.Substring(0, i);
if (int.Parse(section) <= 255 && section[0].ToString() != "0")
{
var otherSections = FetchPossibleIPs(input.Substring(i), currentSection + 1);
foreach (var item in otherSections)
{
possibleIPs.Add($"{section}.{item}");
}
}
}
}
}
return possibleIPs;
}

A sample solution in C# using recursion to solve it.
It uses recursion and backtracking to solve the problem.