1

I am trying to understand the time complexity for this code which calculates IP addresses given a string by splitting the string into 4 parts. Each part is separated by a period i.e. .

public List<String> restoreIpAddresses(String s, int parts) {

    List<String> result = new ArrayList<>();
    if (parts == 1) {
        if (isValidPart(s)) result.add(s);
        return result;
    }
    
    for (int i = 0; i < s.length(); i++) {
        String first = s.substring(0, i);
        if (!isValidPart(first)) {
            continue;
        }
        
        List<String> previous = restoreIpAddresses(s.substring(i, s.length()), parts - 1);
        
        for (String str: previous) {
            StringBuilder sb = new StringBuilder();
            result.add(first + "." + str);
        }
    }        
    
    return result;
    
}

private boolean isValidPart(String part) {
    if ( (part.length() > 1 && part.startsWith("0")) || 
         (part.length() > 3) || (part.length() == 0)
         (Integer.valueOf(part) > 255) ) return false;
      return true;
    }
}

Since the for loop is O(n), n being the length of the string, and in each iteration the for loop executes for the substring that was passed in the parent for loop, so O(n - 1). So by this logic, the time complexity should be n(n-1)(n-2) ....1 i.e. n! in the worst case, right?

However if I look around (eg. here or here), I see people posting constant time complexity. I am unable to understand. Can someone help me break it down?

Improve this question

1 Answer 1

Reset to default
1
+50

Consider this for generating the IP adresses from above algorithm we have two constraints.

  1. Valid IP is from 0->255. This can be evaluated in constant time.
  2. There will be 4 octets. So the question string should be divided into 4 parts.

Now consider a string 111 111 111 111 of length 12

  1. How many way can you form the first octet? => minimum 1 , maximum 3 ways out of 12 characters. complexity:- O(3)

  2. How many way can you form the second octet? => minimum 0 maximum 3 ways out of 9 character, considering 3 characters are used by first octet. complexity:- O(3)

  3. How many way can you form the third octet? => minimum 0 maximum 3 ways from 6 character, considering 6 characters are used by first and second octet. complexity:- O(3)

  4. How many way can you form the fourth octet with the remaining characters? => There is only one way to form an octet from the remaining 3 characters. considering 9 characters are used by the first, second, and third octet. O(1)

Time complexity Calculation.

Time Complexity = product of complexities of each recursive function
                = O(3)*O(3)*O(3)*O(1)
                = 3*O(3) = O(1) = [constant-time] complexity

So no matter what string you will give as an input all the valid IP addresses can be counted in 27 iterations. Therefore this algorithm is a constant time O(1).

Considering the above understanding the code can be re-written following way


public static List<String> restoreIpAddresses(String s, int position, int parts) {

        List<String> result = new ArrayList<>();
        // O(1) time complexity
        if (parts == 1) {
            if (position < s.length() && isValidPart(s.substring(position))) {
                result.add(s.substring(position));
            }
            return result;
        }

        // Iterate only thrice in each recursive function. O(3) time complexity
        for (int i = position; i <= position + 3; i++) {
            if (i > s.length()) {
                continue;
            }

            String first = s.substring(position, i);
            if (!isValidPart(first)) {
                continue;
            }

            List<String> previous = restoreIpAddresses(s, i , parts - 1);

            for (String str : previous) {
                StringBuilder sb = new StringBuilder();
                result.add(first + "." + str);
            }
        }

        return result;

    }

Note that the above algorithm is one examples of classic backtracking problems. From wiki.

Backtracking is a general algorithm for finding solutions to some computational problems, notably constraint satisfaction problems, that incrementally builds candidates to the solutions, and abandons a candidate ("backtracks") as soon as it determines that the candidate cannot possibly be completed to a valid solution

PS:- The example 111 111 111 111 is an extreme example and there is only one valid IP 111.111.111.111 address that can be formed from this string. However, the loop/recursion evaluation will happen a maximum of 81 times.

Improve this answer
Sign up to request clarification or add additional context in comments.

7 Comments

So the code I have written above isn't exactly backtracking unless I use the position parameter?
The code that you have written is the same as mine, the isValidPart checks for length 3, though your code doesn't iterate beyond 3 so lesser checks. But the one I have is still backtracking, right? based on the definition?
Both the codes, yours and mine are the same. I have optimized it so it will not iterate beyond 3. As you see any substring with a length of more than 3 is not a valid IP address. For length beyond 3, the isValidPart will always return false.
Yes, The code you and I have written is essentially backtracking. If you see we take a decision, decide if that leads to a solution, If it does not we backtrack. Which is to go one step back in the recursion tree here.
Thanks! Can you add some info wrt the runtime if this was a more generic problem. Basically is my runtime assessment correct where I use the factorial in a generic case?
|

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Start asking to get answers

Find the answer to your question by asking.

Ask question

Explore related questions

See similar questions with these tags.