Leetcode 93. Restore IP Addresses

Problem Explanation

The problem is to find all the possible valid IP address from a given string of digits.

An Internet Protocol address (IP address) is a numerical label assigned to each device participating in a computer network that uses the Internet Protocol for communication. An IP address serves two principal functions: host or network interface identification and location addressing.

A valid IP address must be in the form of xxx.xxx.xxx.xxx, where xxx is a number from 0 to 255.

You need to split the digits of the input string into four different parts such that each part should be a valid xxx for an IP address.

Example:

If the input string is "25525511135", the possible valid IP addresses from this string would be "255.255.11.135" and "255.255.111.35".

Approach for Solution

The solution for this problem can be implemented using Depth-First Search (DFS) algorithm. We can solve the problem recursively by trying to split the string from 1 to 3 parts at a time, checking if each part is valid, recursing on the rest of the string, and adding the valid IP address to the result.

Making use of a helper function to perform depth-first search to find all possible IP addresses and passing path to store the current solution. If the path contains 4 segments and we have used all characters of the string, we add current solution to the result. If not, we skip the current solution.

Let's take an example of input string "25525511135". The algorithm starts with an empty path, and considers 1, 2 or 3 characters at a time, checks if that part is valid. If it's valid, it takes that part, adds it to the path, and moves on to the next part. It does this recursively until it has either used up all the characters or found a valid IP address.

ASCII explanation:

1
2
325525511135
4
5--> 255.255.11.135
6--> 255.255.111.35

Python Solution

1
2python
3class Solution:
4    def restoreIpAddresses(self, s: str) -> List[str]:
5        ans = []
6        self.dfs(s, 0, [], ans)
7        return ans
8
9    def dfs(self, s, start, path, ans):
10        if len(path) == 4 and start == len(s):
11            ans.append('.'.join(path))
12            return 
13        if len(path) == 4 or start == len(s): 
14            return 
15        for length in range(1, 4):
16            if start + length > len(s): 
17                return 
18            if length != 1 and s[start] == '0': 
19                return  # Leading '0'
20            part = s[start:start + length]
21            if int(part) > 255: 
22                return 
23            path.append(part)
24            self.dfs(s, start + length, path, ans)
25            path.pop()

Java Solution

1
2java
3class Solution {
4    public List<String> restoreIpAddresses(String s) {
5        List<String> ans = new ArrayList<>();
6        dfs(s, 0, new ArrayList<>(), ans);
7        return ans;
8    }
9
10    private void dfs(String s, int start, List<String> path, List<String> ans) {
11        if (path.size() == 4 && start == s.length()) {
12            ans.add(String.join(".", path));
13            return;
14        }
15        if (path.size() == 4 || start == s.length()) return;
16        for (int length = 1; length <= 3; ++length) {
17            if (start + length > s.length()) return;
18            if (length > 1 && s.charAt(start) == '0') return;
19            String part = s.substring(start, start + length);
20            if (Integer.valueOf(part) > 255) return;
21            path.add(part);
22            dfs(s, start + length, path, ans);
23            path.remove(path.size() - 1);
24        }
25    }
26}

JavaScript Solution

1
2javascript
3class Solution {
4    restoreIpAddresses(s) {
5        const ans = [];
6        this.dfs(s, 0, [], ans);
7        return ans;
8    }
9
10    dfs(s, start, path, ans) {
11        if (path.length === 4 && start === s.length) {
12            ans.push(path.join('.'));
13            return;
14        }
15        if (path.length === 4 || start === s.length) return;
16        for (let length = 1; length <= 3; length++) {
17            if (start + length > s.length) return;
18            if (length > 1 && s[start] === '0') return;
19            const part = s.substr(start, length);
20            if (parseInt(part, 10) > 255) return;
21            path.push(part);
22            this.dfs(s, start + length, path, ans);
23            path.pop();
24        }
25    }
26}

C# Solution

1
2csharp
3public class Solution {
4    public IList<string> RestoreIpAddresses(string s) {
5        var ans = new List<string>();
6        Dfs(s, 0, new List<string>(), ans);
7        return ans;
8    }
9
10    private void Dfs(string s, int start, List<string> path, List<string> ans) {
11        if (path.Count == 4 && start == s.Length) {
12            ans.Add(string.Join(".", path));
13            return;
14        }
15        if (path.Count == 4 || start == s.Length) return;
16        for (int length = 1; length <= 3; length++) {
17            if (start + length > s.Length) return;
18            if (length > 1 && s[start] == '0') return;
19            var part = s.Substring(start, length);
20            if (int.Parse(part) > 255) return;
21            path.Add(part);
22            Dfs(s, start + length, path, ans);
23            path.RemoveAt(path.Count - 1);
24        }
25    }
26}

C++ Solution

1
2c++
3class Solution {
4public:
5  vector<string> restoreIpAddresses(string s) {
6    vector<string> ans;
7    dfs(s, 0, {}, ans);
8    return ans;
9  }
10 
11private:
12  void dfs(const string& s, int start, vector<string> path, vector<string>& ans) {
13    if (path.size() == 4 && start == s.size()) {
14      ans.push_back(path[0] + "." + path[1] + "." + path[2] + "." + path[3]);
15      return;
16    }
17    if (path.size() == 4 || start == s.size()) return;
18
19    for (int length = 1; length <= 3; ++length) {
20      if (start + length > s.size()) return;
21      if (length > 1 && s[start] == '0') return;
22      string num = s.substr(start, length);
23      if (stoi(num) > 255) return;
24      path.push_back(num);
25      dfs(s, start + length, path, ans);
26      path.pop_back();
27    }
28  }
29};

The main idea behind these solutions is to use DFS to try every possibility and to check the size and the value of each segment to determine if it's valid or not.## Analyzing the Time Complexity

The time complexity of these solutions can be analyzed as follows:

• The total number of possibilities for any IP address is 3^4 = 81 (as any part of IP address can be 1 to 3 digits).
• Thus, the time complexity for all the solutions will be O(1).
• Also, it should be noted that the IP address's makeup influences the amount of time it takes to confirm its validity—specifically, the presence of leading zeroes can result in more calls.

Conclusion

The process of restoring IP addresses is of notable importance, mainly serving as an exercise in the understanding of DFS( Depth-First Search) and the handling of edge cases in a given problem. Based on the principles of DFS, the presented solutions stringently evaluate each possible combination of segments, which must be within the bounds of valid IPV4 addresses.

Moreover, these solutions have been done in different programming languages so that they can cater to a broad range of programming students and professionals that come from different backgrounds.

Putting these factors into consideration, it could be said without a doubt that the presented solutions provide an in-depth overview of the problem and its solution while pushing readers to truly understand how they can approach DFS problems in a clear and streamlined manner.

So put your problem-solving hat on, grab your favourite text editor, and start solving. These solutions are a great starting point but remember - programming is a practical skill, make sure to practice, and soon you'll be writing efficient code in your way. Happy coding!