younger 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
possible valid IP address combinations.

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):
def restoreIpAddresses(self, s):
"""
: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):
def restoreIpAddresses(self, s):
"""
: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
is start with
'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

Please help,thanks!

Answer Source

The issue is probably with this statement:

if s[0] == '0':
        self.restore(s[1:],count+1,path+[0],res)

It strips leading zeroes. If the input is nothing but zeroes, well, then there's nothing left.

Recommended from our users: Dynamic Network Monitoring from WhatsUp Gold from IPSwitch. Free Download