[LeetCode] 093. Restore IP Addresses
-
date_range April 16, 2019 - Tuesday info
Problem (Medium)
Given a string containing only digits, restore it by returning all possible valid IP address combinations.
Example:
- Input: “25525511135”
- Output: [“255.255.11.135”, “255.255.111.35”]
Approach 1: (My Solution - Backtracking)
Idea
Pretty straight forward backtracking intuition.
Solution
# Backtracking
class Solution1:
def restoreIpAddresses(self, s):
"""
:type s: str
:rtype: List[str]
"""
res = []
self.backtrack(res, [], s)
return res
def backtrack(self, res, item, s):
if len(item) == 4:
if len(s):
return
else:
res.append('.'.join(item))
return
if len(s) > 0:
self.backtrack(res, item + [s[:1]], s[1:])
if len(s) > 1 and int(s[:2]) > 9:
self.backtrack(res, item + [s[:2]], s[2:])
if len(s) > 2 and 99 < int(s[:3]) < 256:
self.backtrack(res, item + [s[:3]], s[3:])
Complexity
- Time: O()
- Space: O()
KF