Question

Formatted question description: https://leetcode.ca/all/93.html

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 <= 20
• s consists of digits only.

Algorithm

In this problem, we need to add three dots to an input character string and divide it into four segments, where each segment must be legal. Our task is to find all possible situations that meet the given criteria.

Through previous problem-solving experience, we have learned that whenever a subsequence or registration problem of a string is encountered, we first consider using dynamic programming (DP). On the other hand, when we need to request all possible situations, we first consider using recursion.

In this case, we need to find all possible legal segmentations, which is more in line with the second case, i.e., we must use recursion to solve this problem.

We represent the number of segments that still need to be divided by k. If k equals 0, it means that we have added three dots and formed four segments. At this point, if the string is empty, we save the current divided result. If k is not 0, then for each segment, we try using one, two, and three digits and judge whether it is legal or not. If it is legal, we call recursion to continue dividing the remaining strings and finally sum up all legal combinations.

Code

• import java.util.ArrayList;
import java.util.List;

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);

Solution s = out.new Solution();

System.out.println(each);
}
}

List<String> list = new ArrayList<>();

public class Solution {

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);

}

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 {
private List<String> ans;

ans = new ArrayList<>();
dfs(s, new ArrayList<>());
return ans;
}

private void dfs(String s, List<String> t) {
if (t.size() == 4) {
if ("".equals(s)) {
}
return;
}
for (int i = 1; i < Math.min(4, s.length() + 1); ++i) {
String c = s.substring(0, i);
if (check(c)) {
dfs(s.substring(i), t);
t.remove(t.size() - 1);
}
}
}

private boolean check(String s) {
if ("".equals(s)) {
return false;
}
int num = Integer.parseInt(s);
if (num > 255) {
return false;
}
if (s.charAt(0) == '0' && s.length() > 1) {
return false;
}
return true;
}
}

• // OJ: https://leetcode.com/problems/restore-ip-addresses
// Time: O(1)
// Space: O(1)
class Solution {
private:
vector<string> ans;
void dfs(string &s, int start, int pos, string &ip) {
if (pos == 4) {
if (start == s.size()) ans.push_back(ip);
return;
}
int i = 0;
for (int num = 0; i < 3 && start + i < s.size(); ++i) {
num = num * 10 + s[start + i] - '0';
if (num > 255 || (s[start] == '0' && i)) break;
ip.push_back(s[start + i]);
if (pos < 3) ip.push_back('.');
dfs(s, start + i + 1, pos + 1, ip);
if (pos < 3) ip.pop_back();
}
while (i--) ip.pop_back();
}
public:
string ip;
dfs(s, 0, 0, ip);
return ans;
}
};

• class Solution:
def restoreIpAddresses(self, s: str) -> List[str]:
def check(s):
if not (0 <= int(s) <= 255):
return False
if s[0] == '0' and len(s) > 1:
return False
return True

def dfs(s, t):
if len(t) == 4:
if not s:
ans.append('.'.join(t))
return
for i in range(1, min(4, len(s) + 1)):
if check(s[:i]):
t.append(s[:i])
dfs(s[i:], t)
t.pop()

ans = []
dfs(s, [])
return ans

############

class Solution(object):
"""
:type s: str
:rtype: List[str]
"""
ans = []
n = len(s)

def isValid(num):
if len(num) == 1:
return True
if len(num) > 1 and num[0] != "0" and int(num) <= 255:
return True
return False

for i in range(0, min(3, n - 3)):
a = s[:i + 1]
if not isValid(a):
break
for j in range(i + 1, min(i + 4, n - 2)):
b = s[i + 1:j + 1]
if not isValid(b):
break
for k in range(j + 1, min(j + 4, n - 1)):
c = s[j + 1:k + 1]
d = s[k + 1:]
if not isValid(c):
break
if not isValid(d):
continue
ans.append("{}.{}.{}.{}".format(a, b, c, d))
return ans


• func restoreIpAddresses(s string) []string {
check := func(s string) bool {
if i, _ := strconv.Atoi(s); i > 255 {
return false
}
if s[0] == '0' && len(s) > 1 {
return false
}
return true
}
var ans []string
var dfs func(s string, t []string)
dfs = func(s string, t []string) {
if len(t) == 4 {
if s == "" {
ans = append(ans, strings.Join(t, "."))
}
return
}
for i := 1; i < 4 && i < len(s)+1; i++ {
if check(s[0:i]) {
t = append(t, s[0:i])
dfs(s[i:], t)
t = t[0 : len(t)-1]
}
}
}
var t []string
dfs(s, t)
return ans
}

• using System.Collections.Generic;
using System.Linq;

public class Solution {
if (s.Length > 12) return new List<string>();
var results = new HashSet<string>();
for (var i = 0; i < s.Length - 3; ++i)
{
for (var j = i + 1; j < s.Length - 2; ++j)
{
for (var k = j + 1; k < s.Length - 1; ++k)
{
var part1 = Normalize(s.Substring(0, i + 1));
var part2 = Normalize(s.Substring(i + 1, j - i));
var part3 = Normalize(s.Substring(j + 1, k - j));
var part4 = Normalize(s.Substring(k + 1));

if (part1 != null && part2 != null && part3 != null && part4 != null)
{
}
}
}
}

return results.ToList();
}

private string Normalize(string part)
{
if (part == "0") return part;
if (part[0] == '0') return null;
byte temp = 0;
if (byte.TryParse(part, out temp))
{
return part;
}
else
{
return null;
}
}
}

• 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;
}