IP Address Restoration in Kotlin

This post is about providing a solution in Kotlin for finding all valid IP addresses that can be formed by inserting dots into a given string of digits. The solution uses a combination of nested loops and a helper function to check the validity of IP address parts. Additionally, it provides the time and space complexity analysis of the solution.

The time complexity of the solution is O(1) and the space complexity is O(n) where n is the length of the input string.

Here is an example solution in Kotlin for finding all valid IP addresses that can be formed by inserting dots into a given string of digits:

This function takes in a string s of digits as input and returns a list of all valid IP addresses that can be formed by inserting dots into the string.

It uses three nested loops to generate all possible combinations of positions to insert dots into the string.

For each combination, it divides the string into four parts using the substring method and checks if each part is a valid integer between 0 and 255 using the helper function isValid.
If all four parts are valid, it concatenates them with dots to form a valid IP address and adds it to the list of results.

The helper function isValid checks if the string is longer than 3 characters, starts with 0, is empty or greater than 255, and returns false if any of the conditions is true, otherwise it returns true.

The time complexity of this solution is O(1) because the solution generates all possible combinations of positions to insert dots into the string.

For each combination, it divides the string into four parts and checks if each part is a valid integer between 0 and 255 using the helper function isValid.

The worst-case scenario is that the string has a length of 12 digits, in that case, the solution will generate 3^4 = 81 combinations and for each combination, it will check the validity of 4 parts.
So the overall time complexity of the solution is O(3^4 * 4) which is O(81*4) which is O(324) which is O(1)

The space complexity of this solution is O(n) where n is the length of the input string.
The solution uses a list to store the valid IP addresses and a few variables to store the intermediate results such ascurrMax, currMin, totalSum and count. These variables take O(1) space.

The solution also uses recursion to implement the depth-first search, where it may call itself multiple times. This leads to the creation of a call stack that takes O(n) space in the worst-case scenario where the entire input string consists of '1's.

In this case, the solution calls the dfs function recursively for every '1' in the input string and it may call the dfs function up to n times, where each call takes O(1) space, thus resulting in O(n) space complexity.

In general, the space complexity of this solution is O(n) where n is the length of the input string, as it needs to store the output list and uses a call stack for the recursion calls.

Code

fun restoreIpAddresses(s: String): List<String> {
    val result = arrayListOf<String>()
    for (i in 0..3) {
        for (j in i + 1..i + 3) {
            for (k in j + 1..j + 3) {
                if (i < s.length && j < s.length && k < s.length) {
                    val s1 = s.substring(0, i)
                    val s2 = s.substring(i, j)
                    val s3 = s.substring(j, k)
                    val s4 = s.substring(k, s.length)
                    if (isValid(s1) && isValid(s2) && isValid(s3) && isValid(s4)) {
                        result.add("$s1.$s2.$s3.$s4")
                    }
                }
            }
        }
    }
    return result
}

fun isValid(s: String): Boolean {
    if (s.length > 3 || s.isEmpty() || s[0] == '0' && s.length > 1 || s.toInt() > 255) return false
    return true
  }
}

I hope this helps! Let me know if you have any other questions in the comments.