LeetCode 093 Restore IP Addresses

LeetCode

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: 0 <= s.length <= 20
* s consists of digits only.

题目大意：

给定一个数字字符串，求以分解成合法IP的所有解。IP每段范围是0-255且不能有前缀0，如06

解题思路：

求所有解，所以用DFS

解题步骤：

N/A

注意事项：

1. 用DFS模板，属于结果分组型DFS，dfs函数有k。
2. 两个限制条件，不能含leading zero和数字范围在255内

Python代码：

def restoreIpAddresses(self, s: str) -> List[str]:
	res = []
	self.dfs(s, 0, [], res, 4)
	return res

def dfs(self, s, st, path, res, k):
	if st == len(s) and k == 0:
		res.append('.'.join(path))
		return
	if st == len(s) or k == 0:
		return
	for i in range(st, min(st + 3, len(s))):
		segment = s[st:i + 1]
		if len(segment) > 1 and segment[0] == '0': # no leading 0
			continue
		if int(segment) > 255: # remember
			continue
		path.append(segment)
		self.dfs(s, i + 1, path, res, k - 1)
		path.pop()

算法分析：

时间复杂度为O(1)，空间复杂度O(1), 由于IP固定是4个部分，每个部分最多3位，所以乘法原理第一个dot的选择有三个位置，其他两个dot如此类推，3x3x3=27