Computing All Valid IP Addresses From Raw IP String

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.

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.