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"]
My code:
class Solution:
def restoreIpAddresses(self, s):
"""
:type s: str
:rtype: List[str]
"""
if len(s)>12:
return []
if len(s)<4:
return []
self.result=self.decode_IP(s,len(s),4)
return self.result
def decode_IP(self,s,i,status):
if status==1:
if s[0]=='0' and len(s[:i])>1:
return None
elif s[0]=='0' and len(s[:i])==1:
return ['0']
if int(s[:i])>=256:
return None
return [s[:i]]
min_require=(status-1)*1
max_require=(status-1)*3
use_max=min([3,i-min_require])+1
use_min=max([1,i-max_require])
print('use min %d, use max %d'%(use_min,use_max))
result=[]
for k in range(use_min,use_max):
result1=s[i-k:i]
ip_tmp=int(result1)
if ip_tmp>=256 or (len(s[i-k:i])>1 and s[i-k]=='0'):
continue
result2=self.decode_IP(s,i-k,status-1)
if result2==None:
continue
for item in result2:
result.append(item+'.'+result1)
return result
```python
Solution:
https://leetcode.com/problems/restore-ip-addresses/