93. Restore IP Addresses
String, Backtracking, Review ·Problem Statement
link: LeetCode.cn 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:
Input: s = "25525511135"
Output: ["255.255.11.135","255.255.111.35"]
Input: s = "0000"
Output: ["0.0.0.0"]
Input: s = "101023"
Output: ["1.0.10.23","1.0.102.3","10.1.0.23","10.10.2.3","101.0.2.3"]
Solution Approach
The solution uses a backtracking approach to systematically explore and construct all possible valid IP addresses by inserting dots into the given string, ensuring adherence to the defined conditions for a valid IP address.
Algorithm
- The algorithm starts by checking base cases: ensuring the input string is not empty, its length is between 4 and 12 (inclusive), and initiating an empty result list.
- It employs a recursive backtracking function (backtracking) that explores different segments of the input string, checking each segment for a valid IP address condition (between 0 and 255, without leading zeros).
- The backtracking function continues to explore and build valid IP addresses, updating the current IP address (curIP) and the number of dots inserted (dots). Once it reaches a valid IP address with four segments, it appends it to the result list. The exploration continues until all valid combinations are found.
Implement
class Solution:
def restoreIpAddresses(self, s: str) -> List[str]:
res = []
if not s or len(s) < 4 or len(s) > 12: return []
def backtracking(i, dots, curIP):
if dots == 4 and i == len(s):
res.append(curIP[:-1])
return
if dots > 4:
return
for j in range(i, min(i + 3, len(s))):
if int(s[i:j + 1]) < 256 and (s[i] != "0" or i == j):
backtracking(j + 1, dots + 1, curIP + s[i:j + 1] + '.')
backtracking(0, 0, "")
return res