Restore IP Addresses
MedPrompt
A valid IP address consists of exactly four integers separated by single dots. Each integer is between 0 and 255 (inclusive) and cannot have leading zeros.
- For example,
"0.1.2.201"and"192.168.1.1"are valid IP addresses, but"0.011.255.245","192.168.1.312"and"[email protected]"are invalid IP addresses.
Given a string s containing only digits, return all possible valid IP addresses that can be formed by inserting dots into s. You are not allowed to reorder or remove any digits in s. You may return the valid IP addresses in any order.
Example 1:
Input: s = "25525511135"
Output: ["255.255.11.135","255.255.111.35"]Example 2:
Input: s = "0000"
Output: ["0.0.0.0"]Example 3:
Input: s = "101023"
Output: ["1.0.10.23","1.0.102.3","10.1.0.23","10.10.2.3","101.0.2.3"]
Constraints:
1 <= s.length <= 20sconsists of digits only.
Approaches
2 approaches with complexity analysis and trade-offs.
This approach uses recursion to explore all possible ways to partition the string into four valid parts. A helper function is defined which tries to build a valid IP address part by part. It explores adding a 1-digit, 2-digit, or 3-digit number as the next part of the IP address, and if the part is valid, it recursively calls itself to find the remaining parts. This method is a classic example of backtracking.
Algorithm
- Initialize an empty list
resultto store the valid IP addresses. - If the input string
shas a length less than 4 or greater than 12, it's impossible to form a valid IP, so return the emptyresultlist. - Create a recursive helper function, let's call it
backtrack(startIndex, path).startIndexis the current position in the strings.pathis a list of the IP address segments found so far.
- Base Case for the recursion:
- If the
pathhas 4 segments:- If
startIndexis at the end of the strings, it means we've successfully partitioned the entire string. Join the segments inpathwith dots and add the resulting IP address toresult. - Return from the function.
- If
- If the
- Recursive Step:
- Loop for segment length
ifrom 1 to 3. - Check boundary conditions:
startIndex + imust not exceed the string length. - Extract the potential segment:
segment = s.substring(startIndex, startIndex + i). - Validate the
segment:- It must not have a leading zero unless it is the number 0 itself (e.g.,
"01"is invalid). - Its integer value must be between 0 and 255.
- It must not have a leading zero unless it is the number 0 itself (e.g.,
- If the
segmentis valid:- Add the
segmentto the currentpath. - Make a recursive call:
backtrack(startIndex + i, path). - Backtrack: Remove the
segmentfrom thepathto explore other possibilities.
- Add the
- Loop for segment length
- Start the process by calling
backtrack(0, new ArrayList<>()). - Return the
resultlist.
Walkthrough
We can model this problem as finding all valid partitions of the string. A recursive backtracking approach is a natural fit for such problems.
We define a recursive function, say backtrack(s, startIndex, currentPath, result):
s: The input string.startIndex: The index insfrom where we start looking for the next part.currentPath: A list of strings representing the parts of the IP address found so far.result: The list to store the final valid IP addresses.
The base case for the recursion is when we have found 4 parts (currentPath.size() == 4). If we have also consumed the entire string (startIndex == s.length()), we have found a valid IP address. We join the parts in currentPath with dots and add it to the result.
In the recursive step, we iterate to choose the next part. The part can have a length of 1, 2, or 3 characters. For each possible length, we extract the substring and validate it. A part is valid if its integer value is between 0 and 255, and it doesn't have a leading zero (unless the part is just "0").
If the part is valid, we add it to our currentPath and make a recursive call for the rest of the string. After the recursive call returns, we must "backtrack" by removing the part we just added from currentPath. This allows us to explore other possibilities, such as a part of a different length starting from the same position.
class Solution { public List<String> restoreIpAddresses(String s) { List<String> result = new ArrayList<>(); if (s.length() < 4 || s.length() > 12) { return result; } backtrack(s, 0, new ArrayList<>(), result); return result; } private void backtrack(String s, int startIndex, List<String> currentPath, List<String> result) { if (currentPath.size() == 4) { if (startIndex == s.length()) { result.add(String.join(".", currentPath)); } return; } // Pruning: check if remaining characters can form the remaining parts int remainingLen = s.length() - startIndex; int remainingParts = 4 - currentPath.size(); if (remainingLen < remainingParts || remainingLen > remainingParts * 3) { return; } for (int i = 1; i <= 3 && startIndex + i <= s.length(); i++) { String segment = s.substring(startIndex, startIndex + i); if (isValidSegment(segment)) { currentPath.add(segment); backtrack(s, startIndex + i, currentPath, result); currentPath.remove(currentPath.size() - 1); // Backtrack } } } private boolean isValidSegment(String segment) { if (segment.length() > 1 && segment.startsWith("0")) { return false; } int value = Integer.parseInt(segment); return value >= 0 && value <= 255; }}Complexity
Time
O(1)
Space
O(1)
Trade-offs
Pros
It's a standard and elegant way to solve partitioning problems.
The logic is clear and can be easily adapted to similar problems with different constraints.
Pruning can be added to optimize the search, making it more efficient by avoiding impossible paths early.
Cons
May have slightly more overhead compared to an iterative solution due to recursive function calls and managing the call stack.
For this specific problem with a fixed number of partitions (4), an iterative approach can be more direct and perform slightly better.
This approach avoids recursion and instead uses three nested loops to iterate through all possible positions for the three dots that separate the four parts of an IP address. For each combination of dot positions (which translates to segment lengths), it checks if the resulting four segments form a valid IP address.
Algorithm
- Initialize an empty list
result. - Get the length
nof the input strings. Ifn < 4orn > 12, returnresult. - Use three nested loops, each iterating from 1 to 3, to represent the lengths
i, j, kof the first three IP address segments. - Inside the loops, calculate the length of the fourth segment:
l = n - (i + j + k). - If
lis between 1 and 3 (inclusive), it means we have found a valid partition of the string into four segments of lengthsi, j, k, l. a. Extract the four substrings based on these lengths. b. Validate each of the four substrings. A substring is valid if it doesn't have a leading zero (unless it's "0") and its integer value is at most 255. c. If all four substrings are valid, combine them with dots to form an IP address string and add it to theresultlist. - After the loops complete, return the
resultlist.
Walkthrough
Since a valid IP address always has exactly four parts, we can determine all possible partitions by trying all valid lengths for the first three parts. The length of the fourth part is then determined by the remaining characters.
Each of the four parts can have a length of 1, 2, or 3. We can use three nested loops to represent the lengths of the first three parts.
- The outer loop iterates for the length of the first part,
i, from 1 to 3. - The second loop iterates for the length of the second part,
j, from 1 to 3. - The third loop iterates for the length of the third part,
k, from 1 to 3.
Inside the innermost loop, we calculate the length of the fourth part, l = n - (i + j + k), where n is the total length of the string. If l is also between 1 and 3, we have found a potential partition. We then extract the four substrings corresponding to these lengths and validate each one. The validation rules are the same: the value must be in [0, 255] and no illegal leading zeros.
If all four parts are valid, we construct the IP address string and add it to our result list. This method exhaustively checks all 3*3*3 = 27 possible length combinations for the first three parts, making it very efficient for the given constraints.
class Solution { public List<String> restoreIpAddresses(String s) { List<String> result = new ArrayList<>(); int n = s.length(); if (n < 4 || n > 12) { return result; } for (int i = 1; i <= 3; i++) { for (int j = 1; j <= 3; j++) { for (int k = 1; k <= 3; k++) { if (i + j + k < n && i + j + k >= n - 3) { String s1 = s.substring(0, i); String s2 = s.substring(i, i + j); String s3 = s.substring(i + j, i + j + k); String s4 = s.substring(i + j + k); if (isValid(s1) && isValid(s2) && isValid(s3) && isValid(s4)) { result.add(s1 + "." + s2 + "." + s3 + "." + s4); } } } } } return result; } private boolean isValid(String segment) { if (segment.length() > 1 && segment.startsWith("0")) { return false; } int value = Integer.parseInt(segment); return value <= 255; }}Complexity
Time
O(1)
Space
O(1)
Trade-offs
Pros
Very efficient and direct, likely the fastest solution in practice for this problem.
Avoids the overhead of recursion (function call stack), leading to better performance.
The logic is straightforward for this specific problem where the number of partitions is small and fixed.
Cons
The code with multiple nested loops can be considered less elegant than a recursive solution.
This approach is less flexible. If the number of parts were variable or the constraints more complex, this approach would become much harder to write and maintain.
Solutions
Solution
public class Solution { private IList < string > ans = new List < string > (); private IList < string > t = new List < string > (); private int n; private string s; public IList < string > RestoreIpAddresses(string s) { n = s.Length; this.s = s; dfs(0); return ans; } private void dfs(int i) { if (i >= n && t.Count == 4) { ans.Add(string.Join(".", t)); return; } if (i >= n || t.Count == 4) { return; } int x = 0; for (int j = i; j < i + 3 && j < n; ++j) { x = x * 10 + (s[j] - '0'); if (x > 255 || (j > i && s[i] == '0')) { break; } t.Add(x.ToString()); dfs(j + 1); t.RemoveAt(t.Count - 1); } }}class Solution { private int n ; private String s ; private List < String > ans = new ArrayList <>(); private List < String > t = new ArrayList <>(); public List < String > restoreIpAddresses ( String s ) { n = s . length (); this . s = s ; dfs ( 0 ); return ans ; } private void dfs ( int i ) { if ( i >= n && t . size () == 4 ) { ans . add ( String . join ( "." , t )); return ; } if ( i >= n || t . size () >= 4 ) { return ; } int x = 0 ; for ( int j = i ; j < Math . min ( i + 3 , n ); ++ j ) { x = x * 10 + s . charAt ( j ) - '0' ; if ( x > 255 || ( s . charAt ( i ) == '0' && i != j )) { break ; } t . add ( s . substring ( i , j + 1 )); dfs ( j + 1 ); t . remove ( t . size () - 1 ); } } } ////// import java.util.ArrayList ; import java.util.List ; public class Restore_IP_Addresses { public static void main ( String [] args ) { // @note:@memorize: test substring boundary String a = "abc" ; // a = a.substring(0, 4); // String index out of range: 4 a = a . substring ( 0 , 3 ); // ok System . out . println ( a ); Restore_IP_Addresses out = new Restore_IP_Addresses (); Solution s = out . new Solution (); for ( String each: ( s . restoreIpAddresses ( "25525511135" ))) { System . out . println ( each ); } } List < String > list = new ArrayList <>(); public class Solution { public List < String > restoreIpAddresses ( String s ) { if ( s . length () < 4 || s . length () > 12 || ! s . matches ( "\\d+" )) { return list ; } restore ( s , "" , 0 ); return list ; } // seg: segment, in total 4 private void restore ( String s , String result , int seg ) { if ( seg == 4 ) { if ( s . length () == 0 ) { // remove last "." result = result . substring ( 0 , result . length () - 1 ); list . add ( result ); } return ; } // for (int i = 0; i < 3; i++) { // @note: out of boundary for ( int i = 0 ; i < 3 && i < s . length (); i ++) { String thisSeg = s . substring ( 0 , i + 1 ); if ( isValid ( thisSeg )) { restore ( s . substring ( i + 1 ), result + thisSeg + "." , seg + 1 ); } } } private boolean isValid ( String s ) { // can NOT be: 10.01.1.1 if ( s . length () > 1 && s . startsWith ( "0" )) { return false ; } int n = Integer . valueOf ( s ); if ( n > 255 ) { return false ; } return true ; } } }class Solution {public: vector<string> restoreIpAddresses(string s) { int n = s.size(); vector<string> ans; vector<string> t; function<void(int)> dfs = [&](int i) { if (i >= n && t.size() == 4) { ans.push_back(t[0] + "." + t[1] + "." + t[2] + "." + t[3]); return; } if (i >= n || t.size() >= 4) { return; } int x = 0; for (int j = i; j < min(n, i + 3); ++j) { x = x * 10 + s[j] - '0'; if (x > 255 || (j > i && s[i] == '0')) { break; } t.push_back(s.substr(i, j - i + 1)); dfs(j + 1); t.pop_back(); } }; dfs(0); return ans; }};class Solution: def restoreIpAddresses(self, s: str) -> List[str]: def check(i: int, j: int) -> int: if s[i] == "0" and i != j: return False return 0 <= int(s[i: j + 1]) <= 255 def dfs(i: int): if i >= n and len(t) == 4: ans . append("." . join(t)) return if i >= n or len(t) >= 4: return for j in range(i, min(i + 3, n)): if check(i, j): t . append(s[i: j + 1]) dfs(j + 1) t . pop() n = len(s) ans = [] t = [] dfs(0) return ansVideo walkthrough
Newsletter
One sharp idea, every week
System design and interview prep — short enough to finish.
No spam. Unsubscribe anytime.
Practice
Same difficulty — related problems to reinforce the pattern.