Description:
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"192.168@1.1"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.
Examples:
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"]Solution in Python:
To solve the problem of generating all possible valid IP addresses from a string containing only digits, we need to carefully place dots in the string such that each segment of the resulting IP address meets the criteria (each segment is between 0 and 255 and does not have leading zeros).
Python
from typing import List
class Solution:
def restoreIpAddresses(self, s: str) -> List[str]:
def is_valid(segment: str) -> bool:
# Check if the segment is a valid IP address part
if len(segment) > 1 and segment[0] == '0':
return False
if 0 <= int(segment) <= 255:
return True
return False
def backtrack(start: int, path: List[str]):
# If we have 4 segments and we've used all the string, it's a valid IP address
if len(path) == 4:
if start == len(s):
result.append('.'.join(path))
return
# Try to create segments of length 1, 2, and 3
for length in range(1, 4):
if start + length <= len(s):
segment = s[start:start + length]
if is_valid(segment):
backtrack(start + length, path + [segment])
result = []
backtrack(0, [])
return resultDetailed Comments on the Code:
- is_valid function:
- This function checks whether a given segment of the string is a valid part of an IP address.
- A segment is invalid if it has a leading zero (unless it is “0” itself) or if its integer value is not between 0 and 255.
- backtrack function:
- This function uses recursion to explore all possible placements of dots in the string.
startis the current position in the string, andpathis the list of segments formed so far.- If we have exactly 4 segments in
pathand we have consumed the entire string (start == len(s)), we join the segments with dots and add the result to the final list.
- Main function restoreIpAddresses:
- Initializes the result list and starts the recursive backtracking process from the beginning of the string.
- Returns the list of valid IP addresses.
Constraints Handling:
- Length Constraints: The function checks and explores segment lengths up to 3 characters (since a valid IP segment can be at most “255”).
- String Length: The solution is efficient and handles the constraints given (1 <= s.length <= 20).
By following this approach, the solution effectively generates all possible valid IP addresses by placing dots in the string while ensuring each segment meets the required criteria.
Solution in Javascript:
JavaScript
/**
* @param {string} s
* @return {string[]}
*/
var restoreIpAddresses = function(s) {
// Function to check if a segment is a valid IP address part
function isValid(segment) {
// A segment is invalid if it has a leading zero and its length is more than 1
if (segment.length > 1 && segment[0] === '0') return false;
// A segment is invalid if its value is not between 0 and 255
let num = parseInt(segment, 10);
return num >= 0 && num <= 255;
}
// Recursive function to perform backtracking
function backtrack(start, path) {
// If we have 4 segments and we've used up all characters, it's a valid IP address
if (path.length === 4) {
if (start === s.length) {
result.push(path.join('.'));
}
return;
}
// Try to create segments of length 1, 2, and 3
for (let length = 1; length <= 3; length++) {
// Ensure the segment does not exceed the length of the string
if (start + length <= s.length) {
let segment = s.substring(start, start + length);
if (isValid(segment)) {
backtrack(start + length, path.concat(segment));
}
}
}
}
// Initialize the result array
let result = [];
// Start the backtracking process
backtrack(0, []);
// Return the final result
return result;
};Solution in Java:
Java
import java.util.ArrayList;
import java.util.List;
class Solution {
public List<String> restoreIpAddresses(String s) {
List<String> result = new ArrayList<>();
if (s == null || s.length() < 4 || s.length() > 12) {
return result; // Early return if the string length is not suitable for an IP address
}
backtrack(s, 0, new ArrayList<>(), result);
return result;
}
private void backtrack(String s, int start, List<String> path, List<String> result) {
// If we have 4 segments and we've used all characters, it's a valid IP address
if (path.size() == 4) {
if (start == s.length()) {
result.add(String.join(".", path));
}
return;
}
// Try to create segments of length 1, 2, and 3
for (int length = 1; length <= 3; length++) {
if (start + length <= s.length()) {
String segment = s.substring(start, start + length);
if (isValid(segment)) {
path.add(segment); // Add the segment to the current path
backtrack(s, start + length, path, result); // Recurse with updated start and path
path.remove(path.size() - 1); // Backtrack by removing the last segment
}
}
}
}
private boolean isValid(String segment) {
// A segment is invalid if it has a leading zero and its length is more than 1
if (segment.length() > 1 && segment.startsWith("0")) {
return false;
}
// A segment is invalid if its value is not between 0 and 255
int num = Integer.parseInt(segment);
return num >= 0 && num <= 255;
}
}Solution in C#:
C#
using System;
using System.Collections.Generic;
public class Solution {
public IList<string> RestoreIpAddresses(string s) {
IList<string> result = new List<string>();
if (string.IsNullOrEmpty(s) || s.Length < 4 || s.Length > 12) {
return result; // Early return if the string length is not suitable for an IP address
}
Backtrack(s, 0, new List<string>(), result);
return result;
}
private void Backtrack(string s, int start, List<string> path, IList<string> result) {
// If we have 4 segments and we've used all characters, it's a valid IP address
if (path.Count == 4) {
if (start == s.Length) {
result.Add(string.Join(".", path));
}
return;
}
// Try to create segments of length 1, 2, and 3
for (int length = 1; length <= 3; length++) {
if (start + length <= s.Length) {
string segment = s.Substring(start, length);
if (IsValid(segment)) {
path.Add(segment); // Add the segment to the current path
Backtrack(s, start + length, path, result); // Recurse with updated start and path
path.RemoveAt(path.Count - 1); // Backtrack by removing the last segment
}
}
}
}
private bool IsValid(string segment) {
// A segment is invalid if it has a leading zero and its length is more than 1
if (segment.Length > 1 && segment.StartsWith("0")) {
return false;
}
// A segment is invalid if its value is not between 0 and 255
int num = int.Parse(segment);
return num >= 0 && num <= 255;
}
}