younger - 1 year ago 95
Python Question

# python recursion

Update:
I forgot the quotation mark... easy fix...

I was trying to do a Leetcode question, the question is #93 Restore IP Address.

Given a string containing only digits, restore it by returning all

For example: Given "25525511135",

return ["255.255.11.135", "255.255.111.35"]. (Order does not matter)

This is the correct code by using DFS:

``````class Solution(object):
"""
:type s: str
:rtype: List[str]
"""
res = []
self.restore(s,0,[],res)
return res
def restore(self,s,count,path,res):
if count == 4:
if not s:
temp = '.'.join(path)
res.append(temp)
else:
return
if not s:
return
if len(s)>2 and int(s[:3])<256 and int(s[:3])>99:
self.restore(s[3:],count+1,path+[s[:3]],res)
if len(s)>1 and int(s[:2])>9:
self.restore(s[2:],count+1,path+[s[:2]],res)
self.restore(s[1:],count+1,path+[s[:1]],res)
return res
``````

This is another approach:

``````class Solution(object):
"""
:type s: str
:rtype: List[str]
"""
res = []
self.restore(s,0,[],res)
return res
def restore(self,s,count,path,res):
if count == 4:
if not s:
temp = '.'.join(path)
res.append(temp)
else:
return
if not s:
return
if s[0] == '0':
#self.restore(s[1:],count+1,path+[0],res)
self.restore(s[1:],count+1,path+['0'],res)
else:
if len(s)>2 and int(s[:3])<256:
self.restore(s[3:],count+1,path+[s[:3]],res)
if len(s)>1:
self.restore(s[2:],count+1,path+[s[:2]],res)
self.restore(s[1:],count+1,path+[s[:1]],res)
return res
``````

The only difference is that the second approach I firstly check if
`s`
`'0'`
.
I do not understand why my second approach is wrong.
take
`s = '0000'`
as an example, the second approach will not write
`'0.0.0.0'`
to
`res`
even
`s == ''`
and
`count = 4`

``````if s[0] == '0':