DFS

A DFS solution.

class Solution:
def restoreIpAddresses(self, s: str) -> List[str]:
res = []
def valid(s):
if len(s)==2:return 10<=int(s)<=99
if len(s)==3:return 100<=int(s)<=255
if len(s)>12:return []
def dfs(s, hist):
if not s:
if len(hist)==4:
res.append('.'.join(hist))
return
if len(s)>=3:
if valid(s[:3]):
dfs(s[3:], hist+[s[:3]])
if len(s)>=2:
if valid(s[:2]):
dfs(s[2:], hist+[s[:2]])
dfs(s[1:], hist+[s[:1]])
dfs(s, [])
return res
Runtime: 44 ms, faster than 14.14% of Python3 online submissions for Restore IP Addresses.Memory Usage: 14 MB, less than 5.56% of Python3 online submissions for Restore IP Addresses.

Can we do better?

Data Scientist/MLE/SWE @takemobi