List all possible combinations of Ip addresses from given String using Recursive Function-CodePudding

I have a String s = "25525511135". How can I find all possible list of IP addresses using recursive function. I wrote a recursive function for this purpose but it is not working. I cannot understand where I am making a mistake.

String s = "25525511135";
int endInd = 1,strInd = 1;
String strNum = s.substring(0,1);

public void restoreIp(String s,List<List<String>> results,List<String> combination,
                          int startIndex, int endIndex,String strNum){

        int num = Integer.parseInt(strNum);
        Integer sumStr = combination.stream().mapToInt(String::length).reduce(0,Integer::sum);

        if (sumStr == s.length() && combination.size() == 4){
            results.add(new ArrayList<>(combination));
            return;
        }

        for (int i = startIndex; i < s.length(); i  ){

            if (num >= 0 && num <= 255 && combination.size() < 4){
                combination.add(""   num);
            } else { break; }

            if (sumStr < s.length() && combination.size() > 4){ break; }

            if (sumStr < s.length() && combination.size() == 4){
                if (endIndex < 4) {
                    endIndex = endIndex   1;
                } else {
                    break;
                }
            }

            restoreIp(s,results,combination,i 1,endIndex,s.substring(i,startIndex   endIndex));
            combination.remove(combination.size() - 1);
        }

    }

I need to collect all possible lists inside results list. Result should look like below:

[
[255,255,11,135]]
[255,255,111,35]
]

CodePudding user response：

A solution to this problem is as follows:

We only need four parameters for our function, the string to parse, the list of results, the current found combination and the index where to start forming a new number of an ip address.

public void restoreIp(String s, List<List<Integer>> results, List<Integer> combination, int startIndex)

We start by declaring the stopping conditions, we stop calling the function when the combination has 4 numbers or the string is fully parsed. If the combination has 4 numbers and the string is fully parsed, we add the combination to the list of results, otherwise we just break from the recursive call.

if (combination.size() == 4 && startIndex >= s.length()) {
    results.add(combination);
    return;
}

if (combination.size() == 4 || startIndex >= s.length()) {
    return;
}

Now the body of the algorithm is to iterate through the string from the startIndex and starts forming new numbers, if the number is zero or greater than 255 we stop iterating because is not a valid ip number otherwise we add the number to the combination and the function call itself.

for (int i = startIndex; i < s.length(); i  ) {
    int number = Integer.parseInt(s.substring(startIndex, i   1));
    if (number == 0 || number > 255) {
        return;
    }
    List<Integer> newCombination = new ArrayList<>(combination);
    newCombination.add(number);

    restoreIp(s, results, newCombination, i   1);
}

So the whole code is:

public static void restoreIp(String s, List<List<Integer>> results, List<Integer> combination, int startIndex) {
    if (combination.size() == 4 && startIndex >= s.length()) {
        results.add(combination);
        return;
    }
    
    if (combination.size() == 4 || startIndex >= s.length()) {
        return;
    }
    
    for (int i = startIndex; i < s.length(); i  ) {
        int number = Integer.parseInt(s.substring(startIndex, i   1));
        if (number == 0 || number > 255) {
            return;
        }
        List<Integer> newCombination = new ArrayList<>(combination);
        newCombination.add(number);
    
        restoreIp(s, results, newCombination, i   1);
    }
}

Testing with:

String str = "17125120120";
List<List<Integer>> result = new ArrayList<>();
restoreIp(str, result, new ArrayList<>(), 0);
System.out.println(result);

will generate:

[[17, 125, 120, 120], [171, 25, 120, 120], [171, 251, 20, 120], [171, 251, 201, 20]]

and with: s = "25525511135"

[[255, 255, 11, 135], [255, 255, 111, 35]]