Given a string s containing only digits, return all possible valid IP addresses that can be formed by inserting dots into s. A valid IP address consists of exactly four integers, each between 0 and 255, separated by dots, and with no leading zeros.
Input: s = "25525511135" → Output: ["255.255.11.135","255.255.111.35"]Input: s = "0000" → Output: ["0.0.0.0"]
Use backtracking: at each step, try taking 1, 2, or 3 characters as the next octet. Validate each segment (no leading zeros, value 0-255). Stop when 4 parts are formed.
- Backtrack with parameters: current index in s, list of parts so far.
- If parts.size()==4 and idx==s.length(), add joined result.
- Try lengths 1, 2, 3 for the next segment; validate each.
- Prune if remaining characters cannot form enough (or too many) segments.
import java.util.*;
class Solution {
public List<String> restoreIpAddresses(String s) {
List<String> result = new ArrayList<>();
backtrack(s, 0, new ArrayList<>(), result);
return result;
}
private void backtrack(String s, int idx, List<String> parts, List<String> result) {
if (parts.size() == 4) {
if (idx == s.length()) result.add(String.join(".", parts));
return;
}
int remaining = 4 - parts.size();
int charsLeft = s.length() - idx;
if (charsLeft < remaining || charsLeft > remaining * 3) return;
for (int len = 1; len <= 3 && idx + len <= s.length(); len++) {
String seg = s.substring(idx, idx + len);
if (seg.length() > 1 && seg.charAt(0) == '0') break;
if (Integer.parseInt(seg) > 255) break;
parts.add(seg);
backtrack(s, idx + len, parts, result);
parts.remove(parts.size() - 1);
}
}
}
- Time Complexity: O(1) — at most 3^4 = 81 candidates
- Space Complexity: O(1) — constant max parts