Given a string S containing only digits, Your task is to complete the function genIp() which returns a vector containing all possible combinations of valid IPv4 IP addresses and takes only a string S as its only argument.
Note: Order doesn't matter. A valid IP address must be in the form of A.B.C.D, where A, B, C, and D are numbers from 0-255. The numbers cannot be 0 prefixed unless they are 0.
For string 11211 the IP address possible are 
1.1.2.11
1.1.21.1
1.12.1.1
11.2.1.1
Example 1:
Input:
S = 1111
Output: 1.1.1.1
Example 2:
Input:
S = 55
Output: -1
Your Task:
Your task is to complete the function genIp() which returns a vector containing all possible combinations of valid IPv4 IP addresses or -1 if no such IP address could be generated through the input string S, the only argument to the function.
Expected Time Complexity: O(N * N * N)
Expected Auxiliary Space: O(N * N * N * N)
Constraints:
1<=N<=16
here, N = length of S.
S only contains digits(i.e. 0-9)

Source: geeksforgeeks | Difficulty: EASY
Tags: String algorithms

Data structures

Complete search

Starter code: #Your Function should return a list containing all possible IP address

#No need to worry about order

class Solution:

    def genIp(self, s):

        #Code here

Solutions:
class Solution:

	def valid(self, char):
		if len(char) == 0 or len(char) > 3 or (char[0] == '0' and len(char) > 1) or (int(char) > 255):
			return False
		else:
			return True

	def genIp(self, s):
		n = len(s)
		if len(s) > 12:
			return ['-1']
		ans = []
		for i in range(1, n - 2):
			for j in range(i + 1, n - 1):
				for k in range(j + 1, n):
					a = s[0:i]
					b = s[i:j]
					c = s[j:k]
					d = s[k:n]
					if self.valid(a) and self.valid(b) and self.valid(c) and self.valid(d):
						ans.append(a + '.' + b + '.' + c + '.' + d)
		return ans


class Solution:

	def genIp(self, s):
		res = []
		for i in range(1, 4):
			for j in range(1, 4):
				for k in range(1, 4):
					for l in range(1, 4):
						if i + j + k + l == len(s):
							c1 = s[0:i]
							c2 = s[i:i + j]
							c3 = s[i + j:i + j + k]
							c4 = s[i + j + k:i + j + k + l]
							if c1 != '' and c2 != '' and (c3 != '') and (c4 != ''):
								(c1, c2, c3, c4) = (int(c1), int(c2), int(c3), int(c4))
								if (c1 >= 0 and c1 <= 255) and (c2 >= 0 and c2 <= 255) and (c3 >= 0 and c3 <= 255) and (c4 >= 0 and c4 <= 255):
									x = str(c1) + '.' + str(c2) + '.' + str(c3) + '.' + str(c4)
									if len(x) == len(s) + 3:
										res.append(x)
		return res


class Solution:

	def genIp(self, s):

		def isValid(st):
			if len(st) != len(str(int(st))):
				return False
			st = int(st)
			if st > 255 or st < 0:
				return False
			return True
		vips = []
		for i in range(1, 4):
			s1 = s[:i]
			if not isValid(s1):
				continue
			for j in range(i + 1, min(len(s), i + 4)):
				s2 = s[i:j]
				if not isValid(s2):
					continue
				for k in range(j + 1, min(len(s), j + 4)):
					s3 = s[j:k]
					if not isValid(s3):
						continue
					s4 = s[k:]
					if not isValid(s4):
						continue
					currIp = s1 + '.' + s2 + '.' + s3 + '.' + s4
					vips.append(currIp)
		return vips


class Solution:

	def checkAll(self, a, b, c, d):
		return a <= 255 and b <= 255 and (c <= 255) and (d <= 255)

	def genString(self, a, b, c, d):
		string = str(a) + '.' + str(b) + '.' + str(c) + '.' + str(d)
		return string

	def genIp(self, s):
		lis = []
		for i in range(1, 4):
			for j in range(1, 4):
				for k in range(1, 4):
					for l in range(1, 4):
						if i + j + k + l == len(s):
							a = int(s[0:i])
							b = int(s[i:i + j])
							c = int(s[i + j:i + j + k])
							d = int(s[i + j + k:i + j + k + l])
							if self.checkAll(a, b, c, d):
								str = self.genString(a, b, c, d)
								if len(str) == len(s) + 3:
									lis.append(str)
		return lis


class Solution:

	def genIp(self, s):
		res = []
		restore_ip_helper(s, 4, '', res)
		return res

def restore_ip_helper(s, k, ip, res):
	if k == 0:
		if not s:
			res.append(ip[:-1])
		return
	for i in range(1, 4):
		if len(s) >= i and is_valid(s[:i]):
			restore_ip_helper(s[i:], k - 1, ip + s[:i] + '.', res)

def is_valid(s):
	if len(s) > 3 or (s[0] == '0' and len(s) > 1) or int(s) > 255:
		return False
	return True


class Solution:

	def genIp(self, s):
		self.n = len(s)
		return self.ipfunc(0, s, 0, [], '')

	def ipfunc(self, i, s, count, ans, ip):
		if count == 4:
			if i == self.n:
				ans.append(ip[:-1])
			return ans
		if i >= self.n:
			return ans
		ans = self.ipfunc(i + 1, s, count + 1, ans, ip + s[i] + '.')
		if i + 1 < self.n and s[i] != '0':
			x = int(s[i:i + 2])
			if x in range(0, 256):
				ans = self.ipfunc(i + 2, s, count + 1, ans, ip + str(x) + '.')
		if i + 2 < self.n and s[i] != '0':
			x = int(s[i:i + 3])
			if x in range(0, 256):
				ans = self.ipfunc(i + 3, s, count + 1, ans, ip + str(x) + '.')
		return ans


class Solution:

	def genIp(self, s):
		n = len(s)
		l = []
		if n < 4 or n > 12 or int(s) > 255255255255:
			return []
		for i in range(3):
			if int(s[:i + 1]) < 256 and (not s[:i + 1].startswith('0')) or s[:i + 1] == '0':
				for j in range(i + 1, i + 4):
					if int(s[i + 1:j + 1]) < 256 and (not s[i + 1:j + 1].startswith('0')) or s[i + 1:j + 1] == '0':
						for k in range(j + 1, n - 1):
							if int(s[j + 1:k + 1]) < 256 and (not s[j + 1:k + 1].startswith('0')) or s[j + 1:k + 1] == '0':
								if int(s[k + 1:]) < 256 and (not s[k + 1:].startswith('0')) or s[k + 1:] == '0':
									l.append(s[:i + 1] + '.' + s[i + 1:j + 1] + '.' + s[j + 1:k + 1] + '.' + s[k + 1:])
		return l


class Solution:

	def genIp(self, s):
		s1 = 0
		s2 = 0
		s3 = 0
		s4 = 0
		arr = []
		for i in range(len(s)):
			for j in range(i + 1, len(s)):
				for k in range(j + 1, len(s)):
					s1 = s[:i]
					s2 = s[i:j]
					s3 = s[j:k]
					s4 = s[k:]
					if s1 != '' and s2 != '' or s3 != '' or s4 != '':
						try:
							if len(s1) > 1 and s1[0] == '0' or (len(s2) > 1 and s2[0] == '0') or (len(s3) > 1 and s3[0] == '0') or (len(s4) > 1 and s4[0] == '0'):
								continue
							elif int(s1) >= 0 and int(s1) <= 255 and (int(s2) >= 0) and (int(s2) <= 255) and (int(s3) >= 0) and (int(s3) <= 255) and (int(s4) >= 0) and (int(s4) <= 255):
								v = '{}.{}.{}.{}'.format(s1, s2, s3, s4)
								arr.append(v)
						except:
							pass
		return arr


class Solution:

	def genIp(self, s):

		def isValid(s):
			if len(s) > 3 or len(s) == 0 or (s[0] == '0' and len(s) > 1) or (int(s) > 255):
				return False
			return True
		res = []
		for i in range(1, len(s) - 2):
			for j in range(i, len(s) - 1):
				for k in range(j, len(s)):
					if isValid(s[:i]) and isValid(s[i:j]) and isValid(s[j:k]) and isValid(s[k:]):
						res.append(s[:i] + '.' + s[i:j] + '.' + s[j:k] + '.' + s[k:])
		if len(res) > 0:
			return res
		return ['-1']


class Solution:

	def genIp(self, s):
		n = len(s)
		if n < 4 or n > 12:
			return [-1]
		ans = []
		for a in range(1, 4):
			for b in range(1, 4):
				for c in range(1, 4):
					for d in range(1, 4):
						if a + b + c + d == n:
							A = int(s[:a])
							B = int(s[a:a + b])
							C = int(s[a + b:a + b + c])
							D = int(s[a + b + c:a + b + c + d])
							if A <= 255 and B <= 255 and (C <= 255) and (D <= 255):
								temp = str(A) + '.' + str(B) + '.' + str(C) + '.' + str(D)
								if len(temp) == n + 3:
									ans.append(temp)
		return ans


class Solution:

	def genIp(self, s):
		sz = len(s)
		if sz > 12:
			return []
		snew = s
		l = []
		for i in range(1, sz - 2):
			for j in range(i + 1, sz - 1):
				for k in range(j + 1, sz):
					snew = snew[:k] + '.' + snew[k:]
					snew = snew[:j] + '.' + snew[j:]
					snew = snew[:i] + '.' + snew[i:]
					if self.is_valid(snew):
						l.append(snew)
					snew = s
		return l

	def is_valid(self, ip):
		ip = ip.split('.')
		for i in ip:
			if len(i) > 3 or int(i) < 0 or int(i) > 255:
				return False
			if len(i) > 1 and int(i) == 0:
				return False
			if len(i) > 1 and int(i) != 0 and (i[0] == '0'):
				return False
		return True


class Solution:

	def genIp(self, s):
		res = []
		part = []

		def dfs(s):
			if len(s) == 0 and len(part) == 4:
				res.append('.'.join(part.copy()))
				return
			if len(s) == 0 or len(part) == 4:
				return
			if int(s[0]) == 0:
				part.append('0')
				dfs(s[1:])
				part.pop()
			else:
				for j in range(len(s)):
					if 0 <= int(s[:j + 1]) < 256:
						part.append(s[:j + 1])
						dfs(s[j + 1:])
						part.pop()
		dfs(s)
		return res if len(res) else [-1]


def solve(i, cnt, temp, s, ans):
	if i == len(s):
		return
	else:
		cur = ''
		y = len(s) - 1
		term = min(i + 2, y)
		flag = True
		x = i
		while x <= term:
			cur += s[x]
			if int(cur) > 255 or (int(cur) == 0 and len(cur) > 1) or (int(cur) > 0 and cur[0] == '0'):
				flag = False
				break
			if cnt > 0:
				cur += '.'
				solve(x + 1, cnt - 1, temp + cur, s, ans)
				cur = cur[:-1]
			x += 1
		if cnt == 0 and flag and (x == len(s)):
			temp += cur
			ans.append(temp)
			return

class Solution:

	def genIp(self, s):
		ans = []
		solve(0, 3, '', s, ans)
		return ans


class Solution:

	def genIp(self, s):
		n = len(s)
		if n < 4 or n > 12:
			return []
		res = []
		for i in range(1, n - 2):
			for j in range(i + 1, n - 1):
				for k in range(j + 1, n):
					if n - k > 3:
						continue
					a = int(s[:i])
					b = int(s[i:j])
					c = int(s[j:k])
					d = int(s[k:])
					if a > 255 or b > 255 or c > 255 or (d > 255):
						continue
					ip = str(a) + '.' + str(b) + '.' + str(c) + '.' + str(d)
					if len(ip) == n + 3:
						res.append(ip)
		return res


class Solution:

	def genIp(self, s):
		ans = []

		def solve(s, q):
			if len(s) == 0:
				if len(q) == 4:
					ans.append('.'.join(q))
				return
			for i in range(1, len(s) + 1):
				if 0 <= int(s[:i]) < 256 and (len(s[:i]) == 1 and int(s[:i]) == 0 or s[:i][0] != '0'):
					solve(s[i:], q + [s[:i]])
				else:
					break
		solve(s, [])
		return ans


class Solution:

	def check(self, s):
		if s == '':
			return False
		if s[0] == '0' and s != '0':
			return False
		if int(s) > 255:
			return False
		return True

	def hellp(self, arr, i, j, k, n):
		s1 = arr[:i + 1]
		s2 = arr[i + 1:j + 1]
		s3 = arr[j + 1:k + 1]
		s4 = arr[k + 1:n]
		s1 = ''.join(s1)
		s2 = ''.join(s2)
		s3 = ''.join(s3)
		s4 = ''.join(s4)
		if self.check(s1) and self.check(s2) and self.check(s3) and self.check(s4):
			return s1 + '.' + s2 + '.' + s3 + '.' + s4
		no = ''
		return no

	def genIp(self, s):
		ar = list(s)
		n = len(s)
		lis = []
		for i in range(n - 2):
			for j in range(i + 1, n - 1):
				for k in range(j + 1, n):
					res = self.hellp(ar, i, j, k, n)
					if res != '':
						lis.append(res)
		return lis


class Solution:

	def genIp(self, s):
		ans = []

		def valid(ip):
			if int(ip) > 256 or (len(ip) > 1 and ip.startswith('0')):
				return False
			return True

		def generate(sofar, s, n=4):
			nonlocal ans
			if s == '':
				if n == 0:
					ans.append(sofar[1:])
				return
			for i in range(1, len(s) + 1):
				if valid(s[:i]):
					generate(sofar + '.' + s[:i], s[i:], n - 1)
		generate('', s)
		return ans


class Solution:

	def genIp(self, s):
		n = len(s)
		if n < 4 or n > 12:
			return []
		result = []
		for i in range(1, n - 2):
			for j in range(i + 1, n - 1):
				for k in range(j + 1, n):
					if n - k > 3:
						continue
					a = s[:i]
					b = s[i:j]
					c = s[j:k]
					d = s[k:]
					if len(a) > 1 and a[0] == '0' or (len(b) > 1 and b[0] == '0') or (len(c) > 1 and c[0] == '0') or (len(d) > 1 and d[0] == '0'):
						continue
					if int(a) <= 255 and int(b) <= 255 and (int(c) <= 255) and (int(d) <= 255):
						result.append(a + '.' + b + '.' + c + '.' + d)
		return result


class Solution:

	def genIp(self, s):
		self.result = []
		self.backtrack(s, [], 0)
		return self.result

	def backtrack(self, s, temp, start):
		if start == len(s) and len(temp) == 4:
			self.result.append('.'.join(temp))
			return
		if len(temp) == 4:
			return
		for i in range(start, min(start + 3, len(s))):
			num_str = s[start:i + 1]
			if self.is_valid(num_str):
				temp.append(num_str)
				self.backtrack(s, temp, i + 1)
				temp.pop()

	def is_valid(self, num_str):
		if len(num_str) == 0 or len(num_str) > 3:
			return False
		if num_str[0] == '0' and len(num_str) > 1:
			return False
		num = int(num_str)
		return num >= 0 and num <= 255


def rec(s, i, st, ans, k):
	if i == len(s):
		if k == 0:
			ans.append(st[:-1])
		return
	if k == 0:
		return
	if s[i] == '0':
		rec(s, i + 1, st + '0' + '.', ans, k - 1)
	else:
		temp = ''
		for j in range(i, len(s)):
			temp += s[j]
			if int(temp) <= 255:
				rec(s, j + 1, st + temp + '.', ans, k - 1)
			else:
				break

class Solution:

	def genIp(self, s):
		ans = []
		rec(s, 0, '', ans, 4)
		return ans


class Solution:

	def genIp(self, s):
		res = []
		if len(s) > 12:
			return ['-1']

		def sol(i, curStr, dots):
			if dots == 4 and i == len(s):
				res.append(curStr[:-1])
			if dots > 4:
				return
			for j in range(i, min(len(s), i + 3)):
				if int(s[i:j + 1]) < 256 and (i == j or s[i] != '0'):
					sol(j + 1, curStr + s[i:j + 1] + '.', dots + 1)
		sol(0, '', 0)
		return res

	def valid(self, char):
		if len(char) == 0 or len(char) > 3 or (char[0] == '0' and len(char) > 1) or (int(char) > 255):
			return False
		else:
			return True

	def genIp2(self, s):
		n = len(s)
		if len(s) > 12:
			return ['-1']
		ans = []
		for i in range(1, n - 2):
			for j in range(i + 1, n - 1):
				for k in range(j + 1, n):
					a = s[0:i]
					b = s[i:j]
					c = s[j:k]
					d = s[k:n]
					if self.valid(a) and self.valid(b) and self.valid(c) and self.valid(d):
						ans.append(a + '.' + b + '.' + c + '.' + d)
		return ans


class Solution:

	def valid(self, char):
		if len(char) == 0 or len(char) > 3 or (char[0] == '0' and len(char) > 1) or (int(char) > 255):
			return False
		else:
			return True

	def genIp(self, s):
		n = len(s)
		ans = []
		for i in range(1, n - 2):
			for j in range(i + 1, n - 1):
				for k in range(j + 1, n):
					A = s[0:i]
					B = s[i:j]
					C = s[j:k]
					D = s[k:n]
					if self.valid(A) and self.valid(B) and self.valid(C) and self.valid(D):
						ans.append(A + '.' + B + '.' + C + '.' + D)
		return ans


class Solution:

	def genIp(self, s):
		n = len(s)
		ans = []
		for i in range(n):
			for j in range(i, n):
				for k in range(j, n):
					a = s[:i]
					b = s[i:j]
					c = s[j:k]
					d = s[k:]
					if valid(a, b, c, d):
						ans.append('.'.join([a, b, c, d]))
		return ans

def valid(a, b, c, d):
	if not a or not b or (not c) or (not d):
		return False
	if len(a) > 1 and a[0] == '0' or int(a) > 255:
		return False
	if len(b) > 1 and b[0] == '0' or int(b) > 255:
		return False
	if len(c) > 1 and c[0] == '0' or int(c) > 255:
		return False
	if len(d) > 1 and d[0] == '0' or int(d) > 255:
		return False
	return True


class Solution:

	def genIp(self, s):
		sn = len(s)
		if sn < 3:
			return []
		if sn > 3 * 4:
			return []
		ans = []

		def rec(s, left, right, path):
			if right - left + 1 < 1:
				if len(path) == 4:
					ans.append('.'.join(path))
				return
			if len(path) >= 4:
				return
			for i in range(min(3, right - left + 1)):
				cur = s[left:left + i + 1]
				if cur[0] == '0':
					if len(cur) != 1:
						continue
				if int(cur) > 255:
					continue
				path.append(cur)
				rec(s, left + i + 1, right, path)
				path.pop()
		path = []
		rec(s, 0, sn - 1, path)
		return ans


class Solution:

	def genIp(self, s):
		arr = []
		for i in range(1, 4):
			for j in range(i + 1, i + 4):
				for k in range(j + 1, j + 4):
					address = s[:i] + '.' + s[i:j] + '.' + s[j:k] + '.' + s[k:]
					arr.append(address)
		output = []
		for item in arr:
			brr = item.split('.')
			flag = True
			for cell in brr:
				if not cell:
					flag = False
					break
				if len(cell) > 1 and cell[0] == '0':
					flag = False
					break
				if int(cell) > 255:
					flag = False
					break
			if flag:
				output.append(item)
		return output


class Solution:

	def genIp(self, s):
		result = []
		if len(s) > 12:
			return result
		for i in range(1, 4):
			for j in range(1, 4):
				for k in range(1, 4):
					for l in range(1, 4):
						if i + j + k + l == len(s):
							a = int(s[:i])
							b = int(s[i:i + j])
							c = int(s[i + j:i + j + k])
							d = int(s[i + j + k:])
							if a <= 255 and b <= 255 and (c <= 255) and (d <= 255):
								ip_address = str(a) + '.' + str(b) + '.' + str(c) + '.' + str(d)
								if len(ip_address) == len(s) + 3:
									result.append(ip_address)
		return result


class Solution:

	def is_valid(self, st):
		ips = st.split('.')
		for i in ips:
			if len(i) > 3 or int(i) < 0 or int(i) > 255:
				return False
			if len(i) > 1 and int(i) == 0:
				return False
			if len(i) > 1 and i[0] == '0':
				return False
		return True

	def genIp(self, s):
		st = s
		n = len(s)
		if n > 12:
			return []
		ans = []
		for i in range(1, n - 2):
			for j in range(i + 1, n - 1):
				for k in range(j + 1, n):
					st = st[:k] + '.' + st[k:]
					st = st[:j] + '.' + st[j:]
					st = st[:i] + '.' + st[i:]
					if self.is_valid(st):
						ans.append(st)
					st = s
		return ans


class Solution:

	def genIp(self, s):
		ls = []
		sz = len(s)
		if sz > 12 or sz < 4:
			ls.append(-1)
			return ls

		def check(IP):
			IP = IP.split('.')
			for i in IP:
				if len(i) > 3 or int(i) < 0 or int(i) > 255:
					return False
				if len(i) > 1 and i[0] == '0':
					return False
			return True
		IP = s
		for i in range(1, sz - 2):
			for j in range(i + 1, sz - 1):
				for k in range(j + 1, sz):
					IP = IP[:k] + '.' + IP[k:]
					IP = IP[:j] + '.' + IP[j:]
					IP = IP[:i] + '.' + IP[i:]
					if check(IP):
						ls.append(IP)
					IP = s
		return ls


class Solution:

	def genIp(self, s):
		res = []
		if len(s) < 4 or len(s) > 12:
			return res

		def rec(i, dots, IP):
			if i == len(s) and dots == 4:
				res.append(IP[:-1])
				return
			for j in range(i, min(i + 3, len(s))):
				if int(s[i:j + 1]) < 256 and (i == j or s[i] != '0'):
					rec(j + 1, dots + 1, IP + s[i:j + 1] + '.')
		rec(0, 0, '')
		return res


class Solution:

	def genIp(self, s):
		n = len(s)
		if n < 4 or n > 12:
			return []
		res = []
		for i in range(1, 4):
			for j in range(i + 1, i + 4):
				for k in range(j + 1, j + 4):
					if k < n:
						(s1, s2, s3, s4) = (s[:i], s[i:j], s[j:k], s[k:])
						if is_valid_ip(s1) and is_valid_ip(s2) and is_valid_ip(s3) and is_valid_ip(s4):
							res.append(s1 + '.' + s2 + '.' + s3 + '.' + s4)
		return res

def is_valid_ip(s: str) -> bool:
	if not s or len(s) > 3 or (len(s) > 1 and s[0] == '0'):
		return False
	num = int(s)
	return 0 <= num <= 255


class Solution:

	def genIp(self, S):
		n = len(S)
		ips = []
		for i in range(1, min(4, n - 2)):
			for j in range(i + 1, min(i + 4, n - 1)):
				for k in range(j + 1, min(j + 4, n)):
					a = int(S[:i])
					b = int(S[i:j])
					c = int(S[j:k])
					d = int(S[k:])
					if a <= 255 and b <= 255 and (c <= 255) and (d <= 255):
						ip = '{}.{}.{}.{}'.format(a, b, c, d)
						if len(ip) == n + 3:
							ips.append(ip)
		return ips


class Solution:

	def dfs(self, s, m, path, res):
		if m > 4:
			return
		if m == 4 and (not s):
			res.append(path[:-1])
			return
		for i in range(1, len(s) + 1):
			if s[:i] == '0' or (s[0] != '0' and 0 < int(s[:i]) < 256):
				self.dfs(s[i:], m + 1, path + s[:i] + '.', res)

	def genIp(self, s):
		res = []
		self.dfs(s, 0, '', res)
		return res


def isValid(ip):
	ip = ip.split('.')
	for i in ip:
		if len(i) > 3 or int(i) < 0 or int(i) > 255:
			return False
		if len(i) > 1 and int(i) == 0:
			return False
		if len(i) > 1 and int(i) != 0 and (i[0] == '0'):
			return False
	return True

class Solution:

	def genIp(self, s):
		size = len(s)
		if size > 12:
			return []
		snew = s
		result = []
		for i in range(1, size - 2):
			for j in range(i + 1, size - 1):
				for k in range(j + 1, size):
					snew = snew[:k] + '.' + snew[k:]
					snew = snew[:j] + '.' + snew[j:]
					snew = snew[:i] + '.' + snew[i:]
					if isValid(snew):
						result.append(snew)
					snew = s
		return result


class Solution:

	def genIp(self, s):

		def check(s):
			m = len(s)
			if m > 0 and m <= 3:
				if int(s) <= 255 and int(s) >= 0 and (str(int(s)) == s):
					return True
			return False
		n = len(s)
		result = []
		for i in range(0, n - 3):
			for j in range(i + 1, n - 2):
				for k in range(j + 1, n - 1):
					s1 = s[0:i + 1]
					s2 = s[i + 1:j + 1]
					s3 = s[j + 1:k + 1]
					s4 = s[k + 1:]
					if check(s1) and check(s2) and check(s3) and check(s4):
						temp = s1 + '.' + s2 + '.' + s3 + '.' + s4
					else:
						temp = ''
					if len(temp) > 0:
						result.append(temp)
		return result


class Solution:

	def genIp(self, s):

		def isvalid(st):
			if len(st) != len(str(int(st))):
				return False
			st = int(st)
			if st > 255 or st < 0:
				return False
			return True
		ans = []
		for i in range(1, 4):
			s1 = s[0:i]
			if not isvalid(s1):
				continue
			for j in range(i + 1, min(len(s), i + 4)):
				s2 = s[i:j]
				if not isvalid(s2):
					continue
				for k in range(j + 1, min(len(s), j + 4)):
					s3 = s[j:k]
					if not isvalid(s3):
						continue
					s4 = s[k:]
					if not isvalid(s4):
						continue
					total = s1 + '.' + s2 + '.' + s3 + '.' + s4
					ans.append(total)
		return ans


class Solution:

	def genIp(self, s):
		length = len(s)
		if length < 4 and length > 12:
			return []
		ans = []
		ssf = ''
		idx = 0
		self.solve(s, ans, ssf, idx, 3)
		return ans if len(ans) else []

	def solve(self, s, ans, ssf, idx, dots):
		if len(s) == 0:
			return
		if dots == 0:
			temp = ssf.split('.')
			temp.pop()
			temp.append(s)
			if all((x[0] != '0' for x in temp if len(x) > 1)):
				if all((0 <= int(x) <= 255 for x in temp)):
					res = '.'.join(temp)
					ans.append(res)
			return
		for i in range(len(s)):
			temp = s[0:i + 1]
			temp = temp + '.'
			self.solve(s[i + 1:], ans, ssf + temp, idx, dots - 1)


class Solution:

	def genIp(self, s):
		res = []
		for a in range(1, 4):
			for b in range(1, 4):
				for c in range(1, 4):
					for d in range(1, 4):
						if a + b + c + d == len(s):
							A = int(s[0:a])
							B = int(s[a:a + b])
							C = int(s[a + b:a + b + c])
							D = int(s[a + b + c:a + b + c + d])
							if A <= 255 and B <= 255 and (C <= 255) and (D <= 255):
								if len(str(A) + '.' + str(B) + '.' + str(C) + '.' + str(D)) == len(s) + 3:
									t = str(A) + '.' + str(B) + '.' + str(C) + '.' + str(D)
									res.append(t)
		return res


class Solution:

	def genIp(self, s):
		res = []
		if len(s) > 12:
			return res

		def b(i, dots, c):
			if dots == 4 and i == len(s):
				res.append(c[:-1])
				return
			elif dots > 4:
				return
			else:
				for j in range(i, min(i + 3, len(s))):
					if int(s[i:j + 1]) < 256 and (i == j or s[i] != '0'):
						b(j + 1, dots + 1, c + s[i:j + 1] + '.')
		b(0, 0, '')
		return res


class Solution:

	def genIp(self, S):
		results = []
		n = len(S)

		def is_valid(segment):
			if len(segment) > 1 and segment[0] == '0':
				return False
			return int(segment) <= 255

		def dfs(start, segments, result):
			if len(segments) == 4:
				if start == n:
					results.append('.'.join(segments))
				return
			for end in range(start, min(start + 3, n)):
				segment = S[start:end + 1]
				if is_valid(segment):
					dfs(end + 1, segments + [segment], result)
		dfs(0, [], [])
		return results


class Solution:

	def genIp(self, s):

		def isValid(s):
			validSet = set([str(i) for i in range(256)])
			ipArray = s.split('.')
			if len(ipArray) != 4:
				return False
			for item in ipArray:
				if item not in validSet:
					return False
			return True
		size = len(s)
		res = []
		if size > 12:
			return res
		newip = s
		for i in range(1, size - 2):
			for j in range(i + 1, size - 1):
				for k in range(j + 1, size):
					newip = newip[:k] + '.' + newip[k:]
					newip = newip[:j] + '.' + newip[j:]
					newip = newip[:i] + '.' + newip[i:]
					if isValid(newip):
						res.append(newip)
					newip = s
		return res


class Solution:

	def genIp(self, s):
		n = len(s)
		ans = []
		for cut1 in range(1, n):
			A = s[:cut1]
			if str(int(A)) != A or int(A) > 255:
				break
			for cut2 in range(cut1 + 1, n):
				B = s[cut1:cut2]
				if str(int(B)) != B or int(B) > 255:
					break
				for cut3 in range(cut2 + 1, n):
					C = s[cut2:cut3]
					if str(int(C)) != C or int(C) > 255:
						break
					D = s[cut3:]
					if str(int(D)) != D or int(D) > 255:
						continue
					ans.append('{A}.{B}.{C}.{D}'.format(A=A, B=B, C=C, D=D))
		return ans


class Solution:

	def get_components(self, s, i, j, k, out):
		c1 = s[:i + 1]
		c2 = s[i + 1:j + 1]
		c3 = s[j + 1:k + 1]
		c4 = s[k + 1:]
		if int(c1) < 0 or int(c1) > 255 or c1 != str(int(c1)):
			return
		if int(c2) < 0 or int(c2) > 255 or c2 != str(int(c2)):
			return
		if int(c3) < 0 or int(c3) > 255 or c3 != str(int(c3)):
			return
		if int(c4) < 0 or int(c4) > 255 or c4 != str(int(c4)):
			return
		out.append(c1 + '.' + c2 + '.' + c3 + '.' + c4)

	def genIp(self, s):
		out = []
		n = len(s)
		if n == 0:
			return out
		for i in range(n - 3):
			for j in range(i + 1, n - 2):
				for k in range(j + 1, n - 1):
					self.get_components(s, i, j, k, out)
		return out


class Solution:

	def genIp(self, s):

		def isvalid(t):
			sepnums = t.split('.')
			for x in sepnums:
				if x[0] == '0':
					if not len(x) == 1:
						return False
				if not (0 <= int(x) and 255 >= int(x)):
					return False
			return True

		def genIPUtil(t, ans, a):
			if isvalid(t):
				ans.append(t)
			if a == 0:
				return
			c = 0
			for x in range(len(t)):
				if t[x] == '.':
					c += 1
					if c == a:
						undis = t[:x]
						if a != 3:
							for q in range(x + 1, x + len(t) - len(undis)):
								if t[q] == '.':
									break
							dis = t[x:q]
							rest = t[q:]
						else:
							dis = t[x:]
							rest = ''
						leng = len(dis)
						dis_li = list(dis)
						for i in range(leng - 2):
							(dis_li[i], dis_li[i + 1]) = (dis_li[i + 1], dis_li[i])
							genIPUtil(undis + ''.join(dis_li) + rest, ans, a - 1)
		if len(s) < 4:
			return [-1]
		t = ''
		for i in range(3):
			t += s[i]
			t += '.'
		t += s[3:]
		ans = []
		genIPUtil(t, ans, 3)
		return ans


class Solution:

	def genIp(self, s):
		if len(s) < 4:
			return []

		def isValid(s):
			if not s:
				return False
			if len(s) > 3:
				return False
			if int(s) > 255:
				return False
			if len(s) > 1 and s[0] == '0':
				return False
			return True
		ans = []

		def findIps(s):
			nonlocal ans
			for i in range(1, len(s)):
				if isValid(s[0:i]):
					for j in range(i + 1, len(s)):
						if isValid(s[i:j]):
							for k in range(j + 1, len(s)):
								if isValid(s[j:k]):
									if isValid(s[k:]):
										ans.append([s[0:i], s[i:j], s[j:k], s[k:]])
								else:
									break
						else:
							break
				else:
					break
		findIps(s)
		if len(ans):
			return ['.'.join(i) for i in ans]
		else:
			return []


class Solution:

	def genIp(self, s):
		res = []

		def BT(i, address):
			if i == len(s):
				if len(address) == 4:
					res.append('.'.join(map(str, address)))
				return
			if address[-1] != 0 and address[-1] * 10 + int(s[i]) <= 255:
				lastItem = address[-1]
				address[-1] = lastItem * 10 + int(s[i])
				BT(i + 1, address)
				address[-1] = lastItem
			if len(address) < 4:
				address.append(int(s[i]))
				BT(i + 1, address)
				address.pop()
		BT(1, [int(s[0])])
		return res


class Solution:

	def genIp(self, s):
		n = len(s)
		ans = []

		def backtrack(i, dots, currIP):
			if dots == 4 and i == n:
				ans.append(currIP[:-1])
				return
			if dots > 4:
				return
			for j in range(i, min(i + 3, n)):
				if int(s[i:j + 1]) < 256 and (i == j or s[i] != '0'):
					backtrack(j + 1, dots + 1, currIP + s[i:j + 1] + '.')
		backtrack(0, 0, '')
		return ans


class Solution:

	def genIp(self, s):
		res = []
		n = len(s)
		if n > 12:
			return []

		def backtrack(i, dots, curr):
			if dots == 4 and i == n:
				res.append(curr[:-1])
				return
			if dots > 4:
				return
			for j in range(i, min(i + 3, n)):
				if int(s[i:j + 1]) < 256 and (i == j or s[i] != '0'):
					backtrack(j + 1, dots + 1, curr + s[i:j + 1] + '.')
		backtrack(0, 0, '')
		return res


class Solution:

	def genIp(self, s):
		n = len(s)
		ans = []
		for i in range(1, min(4, n + 1)):
			s1 = int(s[0:i])
			if s[0:1] == '0' and i > 1:
				continue
			if s1 >= 0 and s1 <= 255:
				for j in range(i + 1, min(i + 4, n + 1)):
					s2 = int(s[i:j])
					if s[i:i + 1] == '0' and j - i > 1:
						continue
					if s2 >= 0 and s2 <= 255:
						for k in range(j + 1, min(j + 4, n + 1)):
							s3 = int(s[j:k])
							if s[j:j + 1] == '0' and k - j > 1:
								continue
							if s3 >= 0 and s3 <= 255:
								if k < n:
									s4 = int(s[k:])
									if s[k:k + 1] == '0' and n - k > 1:
										continue
									if s4 >= 0 and s4 <= 255:
										val = s[0:i] + '.' + s[i:j] + '.' + s[j:k] + '.' + s[k:]
										ans.append(val)
		return ans


from typing import List

class Solution:

	def genIp(self, S: str) -> List[str]:

		def dfs(s, ip, ips):
			if not s:
				if len(ip) == 4:
					ips.append('.'.join(ip))
				return
			for i in range(1, 4):
				if i <= len(s) and (i == 1 or s[0] != '0') and (int(s[:i]) <= 255):
					dfs(s[i:], ip + [s[:i]], ips)
		ips = []
		dfs(S, [], ips)
		return ips if ips else [-1]


class Solution:

	def genIp(self, s):

		def check(s):
			n = len(s)
			if n <= 0 or n > 3:
				return False
			if s[0] == '0' and n > 1:
				return False
			if int(s) < 0 or int(s) > 255:
				return False
			return True

		def generate(s, i, j, k, n):
			s1 = s[0:i]
			s2 = s[i:j]
			s3 = s[j:k]
			s4 = s[k:n]
			if check(s1) and check(s2) and check(s3) and check(s4):
				return s1 + '.' + s2 + '.' + s3 + '.' + s4
			else:
				return ''
		n = len(s)
		if n < 4:
			return []
		ans = []
		for i in range(n):
			for j in range(i + 1, n):
				for k in range(j + 1, n):
					string = generate(s, i, j, k, n)
					if len(string) > 0:
						ans.append(string)
		return ans