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.
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 <= 20s consists of digits only.
Solutions
Solution 1: DFS
We define a function dfs(i), which represents the list of IP addresses that can be formed starting from the ith position of string s.
The execution steps of function dfs(i) are as follows:
If i is greater than or equal to the length of string s, it means that we have completed the splicing of four segments of the IP address. At this point, we need to check whether it meets the requirements of the four segments of the IP address. If it does, add the current IP to the answer.
If i is less than the length of string s, it means that we still need to splice a segment of the IP address. At this point, we need to determine the value of this segment of the IP address. If the value is greater than 255, or the current position i is 0 and the value of several positions after i is greater than 0, it means that it does not meet the requirements, so we return directly. Otherwise, add it to the IP address list, and continue to search for the next segment of the IP address.
The time complexity is O(n × 3^4), and the space complexity is O(n). Here, n is the length of string s.
PythonJavaC++GoTypeScriptC#
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 ans(code-box)
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);
}
}
}(code-box)
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;
}
};(code-box)
func restoreIpAddresses(s string) (ans []string) {
n := len(s)
t := []string{}
var dfs func(int)
dfs = func(i int) {
if i >= n && len(t) == 4 {
ans = append(ans, strings.Join(t, "."))
return
}
if i >= n || len(t) == 4 {
return
}
x := 0
for j := i; j < i+3 && j < n; j++ {
x = x*10 + int(s[j]-'0')
if x > 255 || (j > i && s[i] == '0') {
break
}
t = append(t, s[i:j+1])
dfs(j + 1)
t = t[:len(t)-1]
}
}
dfs(0)
return
}(code-box)
function restoreIpAddresses(s: string): string[] {
const n = s.length;
const ans: string[] = [];
const t: string[] = [];
const dfs = (i: number): void => {
if (i >= n && t.length === 4) {
ans.push(t.join('.'));
return;
}
if (i >= n || t.length === 4) {
return;
}
let x = 0;
for (let j = i; j < i + 3 && j < n; ++j) {
x = x * 10 + s[j].charCodeAt(0) - '0'.charCodeAt(0);
if (x > 255 || (j > i && s[i] === '0')) {
break;
}
t.push(x.toString());
dfs(j + 1);
t.pop();
}
};
dfs(0);
return ans;
}(code-box)
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);
}
}
}(code-box)
